描述 Description
农场有 N(1≤N≤1000) 个牛棚，每个牛棚都有 1 只奶牛要参加在 X 牛棚举行的奶牛派对．共有 M(1≤M≤100000) 条单向路连接着牛棚，第 i 条踣需要 Ti 的时间来通过．牛们都很懒，所以不管是前去 X 牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？
输入格式 InputFormat
第 1 行: 三个用空格隔开的整数.
第 2 行到第 M+1 行, 每行三个用空格隔开的整数: Ai, Bi, 以及 Ti. 表示一条道路的起点, 终点和需要花费的时间.
输出格式 OutputFormat
唯一一行: 一个整数: 所有参加聚会的奶牛中, 需要花费总时间的最大值.
样例输入 SampleInput
6 20 3
3 2 45
6 1 66
6 2 31
2 4 94
5 3 46
5 2 79
3 1 64
4 3 74
3 5 59
1 6 93
3 6 45
6 4 40
3 4 67
1 3 61
1 2 42
4 2 50
4 1 55
2 6 93
5 4 95
1 4 54
样例输出 SampleOutput
213
来源 Source
Silver
代码 Code
n 太小了于是可以用 Floyd 水过去。。。
如果是节点数略大的题目需要正反向边分别建图跑两次 SPFA.
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff/27.11
int a[1005][1005];
int i,j,t,n,m,l,r,k,s,z,y,x,ans;
int main()
{
scanf("%d%d%d",&n,&m,&s);
for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (i!=j) a[i][j]=inf;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
}
for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++)
{
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
ans=0;
for (i=1;i<=n;i++) ans=max(ans,a[i][s]+a[s][i]);
printf("%d\n",ans);
return 0;
}