望自己成熟稳重善良填满优秀
来自 N (1 ≤ N ≤ 1000)个农场的奶牛的编号分别为1,2, … ,N。现在在农场 X (1 ≤ X ≤ N) 举行聚会。总共有 M (1 ≤ M ≤ 100,000) 条单向通道。路 i 需要时间 Ti 才能通过。每头牛都需要参加聚会并返回,而且它们均选择花费时间最短的路线。
问:在所有的奶牛中,所花费的最长时间为多少?
Input
第一行包含三个整数N,M,X。
在接下来的M行中,每行都包括三个整数A,B和T,表示从农场A到B需要花费时间T。
Output
输出奶牛所花的最大时间。
Sample Input
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
Sample Output
10
因为道路是单向的,所以来回的最短路不一定是同一条,用Dijkstra求两次:以x为起点一个正向走一个逆向走。逆向走的时候改变一下矩阵的顺序就可。具体细节见代码叭
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair<int, int> PII; #define I_int ll #define PI 3.1415926535898 inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); puts(""); } ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1100,inf=0x3f3f3f3f,mod=1e9+7; int n,m,x; int g[maxn][maxn]; int dist[maxn],dist1[maxn]; bool st[maxn]; void dijkstra(int s){ memset(dist,0x3f,sizeof dist); memset(st,0,sizeof st); dist[s]=0; for(int i=1;i<=n;i++){ int t=-1; for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]); st[t]=1; } } void dijkstra1(int s){ memset(dist1,0x3f,sizeof dist1); memset(st,0,sizeof st); dist1[s]=0; for(int i=1;i<=n;i++){ int t=-1; for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist1[t]>dist1[j])) t=j; for(int j=1;j<=n;j++) dist1[j]=min(dist1[j],dist1[t]+g[j][t]);///反向走 st[t]=1; } } int main(){ while(cin>>n>>m>>x){ memset(g,0x3f,sizeof g); while(m--){ int a,b,c; a=read();b=read();c=read(); g[a][b]=min(g[a][b],c); } dijkstra(x);dijkstra1(x); int res=-inf; for(int i=1;i<=n;i++) if(dist1[i]!=inf&&dist[i]!=inf) res=max(res,dist1[i]+dist[i]); out(res); } return 0; }