时间戳

首页 > 技术文章 > cdoj914-方老师分身 I 【dijkstra】

cdoj914-方老师分身 I 【dijkstra】

jiu0821 2015-06-29 11:18 原文

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

方老师分身 I

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

方老师为了开更多讲座，于是他分身了！早上他都在某一个教室分身，然后各个分身分别赶去各个不同的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

Sample InputSample 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。第一次顺着来，第二次逆着来。这里对图的存储不适合前向星，适合矩阵存储，求逆着的边的时候更为方便。

代码：

 1 #include <fstream>
 2 #include <iostream>
 3 #include <vector>
 4 #include <queue>
 5 #include <cstring>
 6 #include <cstdio>
 7 
 8 using namespace std;
 9 
10 const int INF=0x7fffffff;
11 const int N=1005;
12 const int M=100005;
13 int n,m,x;
14 int a[N][N];
15 int dis[N],dis2[N];
16 bool b[N];
17 typedef pair<int,int> pii;
18 priority_queue<pii,vector<pii>,greater<pii> >p;
19 
20 void dijkstra();
21 void dijkstra2();
22 
23 int main()
24 {
25     //freopen("D:\\input.in","r",stdin);
26     //freopen("D:\\output.out","w",stdout);
27     int t1,t2,t3;
28     scanf("%d%d%d",&n,&m,&x);
29     for(int i=0;i<m;i++){
30         scanf("%d%d%d",&t1,&t2,&t3);
31         a[t1][t2]=t3;
32     }
33     dijkstra();
34     dijkstra2();
35     t1=0;
36     for(int i=1;i<=n;i++)   t1=max(t1,dis[i]+dis2[i]);
37     printf("%d\n",t1);
38     return 0;
39 }
40 void dijkstra(){
41     for(int i=1;i<=n;i++)   dis[i]=INF;
42     dis[x]=0;
43     p.push(make_pair(0,x));
44     while(!p.empty()){
45         pii tp=p.top();
46         p.pop();
47         int tx=tp.second;
48         if(b[tx])   continue;
49         b[tx]=1;
50         for(int i=1;i<=n;i++){
51             if(a[tx][i]&&(!b[i])){
52                 if(dis[i]>dis[tx]+a[tx][i]){
53                     dis[i]=dis[tx]+a[tx][i];
54                     p.push(make_pair(dis[i],i));
55                 }
56             }
57         }
58     }
59 }
60 void dijkstra2(){
61     for(int i=1;i<=n;i++)   dis2[i]=INF;
62     memset(b,0,sizeof(b));
63     dis2[x]=0;
64     p.push(make_pair(0,x));
65     while(!p.empty()){
66         pii tp=p.top();
67         p.pop();
68         int tx=tp.second;
69         if(b[tx])   continue;
70         b[tx]=1;
71         for(int i=1;i<=n;i++){
72             if(a[i][tx]&&(!b[i])){
73                 if(dis2[i]>dis2[tx]+a[i][tx]){
74                     dis2[i]=dis2[tx]+a[i][tx];
75                     p.push(make_pair(dis2[i],i));
76                 }
77             }
78         }
79     }
80 }

推荐阅读