cdoj914-方老师分身 I 【dijkstra】

http://acm.uestc.edu.cn/#/problem/show/914

方老师分身 I

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

方老师为了开更多讲座，于是他分身了！早上他都在某一个教室分身，然后各个分身分别赶去各个不同的n个教室（当然每个教室都要有且只有一个分身）。晚上各个分身都赶回之前分身时的教室，合并成一个人（不需要同时回去）。但是教室间的路十分崎岖，而且是单向的。当然即便只是方老师的分身，那也是相当厉害的，每个分身都会走花费时间最少的路径。方老师想知道他往返走路时间最长的那个分身所花在走路上的时间。题目保证有路可走。

Input

第一行输入三个整数 n, m, x（1≤n≤1000, 1≤m≤100,000, 1≤x≤n）。表示有n个教室，m条路，x为方老师分身的地方。

接下来m行，每行三个数，u, v, t表示从教室u到教室v存在一条单向边，花费时间t（1≤t≤100）。

Output

输出一个整数，往返中走路时间最长的分身所花费的时间。

Sample input and output

4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3

10

题解：两次dijkstra。第一次顺着来，第二次逆着来。这里对图的存储不适合前向星，适合矩阵存储，求逆着的边的时候更为方便。

代码：

 #include <fstream>

 #include <iostream>

 #include <vector>

 #include <queue>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int INF=0x7fffffff;

 const int N=;

 const int M=;

 int n,m,x;

 int a[N][N];

 int dis[N],dis2[N];

 bool b[N];

 typedef pair<int,int> pii;

 priority_queue<pii,vector<pii>,greater<pii> >p;

 void dijkstra();

 void dijkstra2();

 int main()

 {

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     int t1,t2,t3;

     scanf("%d%d%d",&n,&m,&x);

     for(int i=;i<m;i++){

         scanf("%d%d%d",&t1,&t2,&t3);

         a[t1][t2]=t3;

     }

     dijkstra();

     dijkstra2();

     t1=;

     for(int i=;i<=n;i++)   t1=max(t1,dis[i]+dis2[i]);

     printf("%d\n",t1);

     return ;

 }

 void dijkstra(){

     for(int i=;i<=n;i++)   dis[i]=INF;

     dis[x]=;

     p.push(make_pair(,x));

     while(!p.empty()){

         pii tp=p.top();

         p.pop();

         int tx=tp.second;

         if(b[tx])   continue;

         b[tx]=;

         for(int i=;i<=n;i++){

             if(a[tx][i]&&(!b[i])){

                 if(dis[i]>dis[tx]+a[tx][i]){

                     dis[i]=dis[tx]+a[tx][i];

                     p.push(make_pair(dis[i],i));

                 }

             }

         }

     }

 }

 void dijkstra2(){

     for(int i=;i<=n;i++)   dis2[i]=INF;

     memset(b,,sizeof(b));

     dis2[x]=;

     p.push(make_pair(,x));

     while(!p.empty()){

         pii tp=p.top();

         p.pop();

         int tx=tp.second;

         if(b[tx])   continue;

         b[tx]=;

         for(int i=;i<=n;i++){

             if(a[i][tx]&&(!b[i])){

                 if(dis2[i]>dis2[tx]+a[i][tx]){

                     dis2[i]=dis2[tx]+a[i][tx];

                     p.push(make_pair(dis2[i],i));

                 }

             }

         }

     }

 }