题意描述：N头牛要从不同的节点赶到一个节点开会，开完会返回原处，所有的道路都是有向路，求出往返花费时间最长的那头牛花费的时间。
看到这题，第一感觉就是对每个节点用一次Dijkstra，1000的数据量，无情的超时了。看网上大神们的代码，发现用两遍Dijkstra就行了，第一遍是求出从目的地X出发，到达其余点的时间，第二遍还是从X出发，不过要把所有边反向使用。把每个节点两次的时间加一起，求出最大的那个即可。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 1010
#define MAX 200000000
int mp[LEN][LEN];
int N, M, X;
int cost[LEN];
void Dijkstrabk(int f)
{
int i, j;
int s[LEN] = {0};
s[f] = 1;
for(i = 1; i <= N; i++)
if(mp[f][i] != 0)
cost[i] = mp[f][i];
else
cost[i] = MAX;
cost[f] = 0;
for(j = 1; j <= N - 1; j++)
{
int t = f;
int min = MAX;
for(i = 1; i <= N; i++)
if(s[i] == 0 && cost[i] < min)
{
t = i;
min = cost[i];
}
s[t] = 1;
for(i = 1; i <= N; i++)
if(s[i] == 0 && mp[t][i] != 0 && mp[t][i] + cost[t] < cost[i])
cost[i] = mp[t][i] + cost[t];
}
}
void Dijkstracm(int f)
{
int i, j;
int s[LEN] = {0};
s[f] = 1;
for(i = 1; i <= N; i++)
if(mp[i][f] != 0)
cost[i] = mp[i][f];
else
cost[i] = MAX;
cost[f] = 0;
for(j = 1; j <= N - 1; j++)
{
int t = f;
int min = MAX;
for(i = 1; i <= N; i++)
if(s[i] == 0 && cost[i] < min)
{
t = i;
min = cost[i];
}
s[t] = 1;
for(i = 1; i <= N; i++)
if(s[i] == 0 && mp[i][t] != 0 && mp[i][t] + cost[t] < cost[i])
cost[i] = mp[i][t] + cost[t];
}
}
int main()
{
int i, j;
int A, B, T;
int bkcost[LEN];
int cmcost[LEN];
int allcost;
while(scanf("%d%d%d", &N, &M, &X) != EOF)
{
memset(mp, 0, sizeof(mp));
for(i = 0; i < M; i++)//reaa mp
{
scanf("%d%d%d", &A, &B, &T);
if(mp[A][B] == 0)
mp[A][B] = T;
else if(mp[A][B] > T)
mp[A][B] = T;
}
Dijkstrabk(X);
for(i = 1; i <= N; i++)
bkcost[i] = cost[i];
Dijkstracm(X);
allcost = -MAX;
for(i = 1; i <= N; i++)
if(bkcost[i] + cost[i] > allcost)
allcost = bkcost[i] + cost[i];
printf("%d\n", allcost);
}
//system("pause");
}
posted on 2012-08-09 16:18
小鼠标 阅读(223)
评论(0) 编辑 收藏 引用 所属分类:
图论