path

Description

以下摘自是某ACM队某次对话的某民间记载：

……

”接下来来讨论一下关于如何吃饭的问题。“

唰唰唰。画出了一张无向图。

”我们现在处于S点，食堂处于T点。“

指指点点。

”本来吃饭是个很简单的问题，这条路是最短路径，我们顺着走过去就好。“

队长画出了一条最短路径。

”但是你们两个非要提出古怪的要求。“

拿起笔指向其中一人。

”首先是你，想要走一条人最少的路线，让我感到非常头疼，因为这意味着我们可能要绕很远的一段路。“

笔尖一转。

”然后是你，居然非要走一条最阴暗的路线，我已经完全不能够理解你在思考些什么了。“

……

记载到此结束。

我们对这段历史很有兴趣。现在已知上述队长画出的图，以及图中的S、T和各边的权值，求三人所要求的路线。

提示：没有学习过最短路径的同学可以上网查找一下相关资料，推荐使用SPFA或者dijkstra算法。

Input Format

输入的第一行包含一个不超过10的正整数T，表示数据的组数。 接下来有T个部分，每个部分的第一行包括四个正整数n、m、s、t，(1<=n<=1000，0<=m<=10000)，s、t表示起点终点。接下来有m行，第i行描述第i条边的信息，所有权均为正整数，并且不超过32768，格式见样例，并且保证数据中的格式与样例一致。 顶点标号为1~n标号。

Output Format

输出包含T行，每行包括三个正整数分别按顺序表示路径的最小长度和、路径的最少人数和，以及路径的最小亮度值。

Sample Input

13 3 1 3Name: Short but crowd road, From: 1, To: 2, Length: 1, People number: 10, Light: 1;Name: Normal road, From: 2, To: 3, Length: 1, People number: 1, Light: 1;Name: Long but not crowd road, From: 1, To: 3, Length: 10, People number: 1, Light: 1;

Sample Output

2 1 1 此题就是字符串处理加上最短路径问题。 关于最短路径问题经典算法主要有两个.

算法1:

Dijkstra算法步骤如下：

G={V,E}

1. 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值

　　若存在边<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

　　若不存在边<V0,Vi>，d(V0,Vi)为∞

2. 从T中选取一个与S中顶点 有关联边 且 权值最小 的顶点W，加入到S中

3. 对其余T中顶点的 距离值 进行修改： 若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值 (松弛操作)

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止 表示找到了终点

 

Dijkstra就是不断地去寻找、更新. 它的每一次更新都要遍历所有的T中的点, 这个是耗时的最重要原因. 当然可以用队列优化等等策略去改进.

代码如下,这个只是Demo,实际情况超时

//sjtu oj 1105//dijkstra 算法应用#include 
       
        #include 
        
         using namespace std;int main(int argc, char const *argv[]){    int N = 5;    int const INFINITY = 9999999;    //初始化Graph 邻接矩阵    int** Graph = new int*[N+1];    for (int i = 0; i < N+1; ++i){        Graph[i] = new int[N+1];        for (int j = 0; j < N+1; ++j)            Graph[i][j]=0;    }        Graph[1][2]=Graph[2][1]=1;    Graph[1][3]=Graph[3][1]=5;    Graph[2][4]=Graph[4][2]=2;    Graph[2][5]=Graph[5][2]=4;    Graph[3][4]=Graph[4][3]=2;    Graph[3][5]=Graph[5][3]=3;    Graph[4][5]=Graph[5][4]=1;        for (int i = 1; i <= N; ++i){        for (int j=1; j <= N; ++j){            cout<
         
          <<" ";        }        cout<
          
           0 ? Graph[start][i] : INFINITY;    D[start] = 0;//起点自己和自己的距离是0        int* S = new int[N],*Q = new int[N];//S表示所有的已经计算出最短距离的点    int p_S=0,p_Q=0,len_S=1,len_Q=N-1;    S[p_S++] = start;//最开始只有起点在S中    for (int i = 1; i <= N; ++i) if(i!=start)        Q[p_Q++] = i;//把所有非起点的点都加入到Q中            while(len_Q>=1){
     //Q中还有元素 就要从Q里选出一个加到S里        cout<<"S:"<
           
            0)//找到所有和u相连的i点            if(D[v] > D[u]+Graph[u][v])                D[v] = D[u]+Graph[u][v];//更新        }      }        cout<
            
             <
            
           
          
         
        
       

 

 

算法2:

SPFA和BFS很像 只是它允许一个点重复进入待处理队列,因为在不断更新.搭配邻接链表使用更佳

它的基本思想就是 构造一个队列 首元素是起点,然后对和起点相连的每个点进行遍历, 如果可以进行松弛操作,则把这个点也加到处理队列中, 留待继续优化因它而起的其他点.

注意 这个算法无法中途终止 必须到队列为空(为空表示没有要继续优化的点了,所有的最短距离估计值即是最优)

PS:没有进行优化 如果是双端队列可以进行对不同元素,按条件放到头或者尾,从而减少不必要的更新. 

代码如下:

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
              //用SFPA来做 主要的想法是BFS和队列优化 数据结构用邻接链表#define INFINITY 32769using namespace std; struct Edge{ int to; int length; int pepole; int light;}; vector
             
               adjmap[1001];//邻接链表来存储每个点的边集 注意:无向图的处理bool in_queue[1001];//记录某个顶点是否在队列中int D[1001][3]={ 0};//D来存储从起点到某一点的最短距离(暂时的) [0]是length [1]是people [2]是lightint n,m,s,e;//点 边 起点 终点//从字符串里提取信息int getINT(string edge,string tag,string seg=","){ //有点傻..好像按顺序找数字就可以了?两位数不好办吧.. stringstream ss; int res; int start = edge.find(tag) + tag.size(); int end = edge.substr(start).find(seg); ss<
              
               >res;//转换类型 return res;} inline int getWeight(Edge e,int flag){ switch(flag){ case 0: return e.length; case 1: return e.pepole; case 2: return e.light; } return 0;} //返回最"短"路径的权重总和int spfa(int flag){ //spfa不可以像dijsktra那样遇到end中途断掉 必须全部结束 //s=source flag = 0 ,1 ,2 queue
               
                 q;//正要遍历的节点的号码 BFS for (int i = 1; i <= n; ++i)//对所有的点进行初始化 { D[i][flag]=INFINITY; in_queue[i]=false; } q.push(s); in_queue[s]=true; D[s][flag]=0; //初始化完毕 while(!q.empty()){ int u = q.front(); q.pop(); in_queue[u]=false; unsigned long size = adjmap[u].size(); for (int i = 0; i < size; ++i) { int to = adjmap[u][i].to; int weight = getWeight(adjmap[u][i],flag); //判断是否进行松弛操作 if((D[u][flag]
                
                  D[u][flag]+weight)){ //松弛 D[to][flag] = D[u][flag] + weight; if(!in_queue[to]){ in_queue[to]=true; q.push(to); } } } } //对所有边 return D[e][flag];} int main(int argc, char const *argv[]){ int T;cin>>T; for (int i = 0; i < T; ++i) { cin>>n>>m>>s>>e; getchar();//因为第一行的回车没读 要getchar一下 否则RE //初始化邻接链表 for (int i = 0; i < n; ++i) adjmap[i].clear(); //对m个边进行初始化 for (int i = 0; i < m; ++i) { string edge; getline(cin,edge); while(edge=="") //据说有空行... getline(cin,edge); int from,to,pepole,light,length; //读取 from = getINT(edge,"From: "); to = getINT(edge,"To: "); length = getINT(edge,"Length: "); pepole = getINT(edge,"People number: "); light = getINT(edge,"Light: ",";"); Edge e; e.to = to; e.length = length; e.pepole = pepole; e.light = light; adjmap[from].push_back(e); e.to = from;//无向图要处理两次 adjmap[to].push_back(e); } memset(D,0,sizeof(D)); cout<
                 
                  <<" "<
                  
                   <<" "<
                   
                    <