題意描述：N頭牛要從不同的節(jié)點(diǎn)趕到一個(gè)節(jié)點(diǎn)開(kāi)會(huì)，開(kāi)完會(huì)返回原處，所有的道路都是有向路，求出往返花費(fèi)時(shí)間最長(zhǎng)的那頭牛花費(fèi)的時(shí)間。
看到這題，第一感覺(jué)就是對(duì)每個(gè)節(jié)點(diǎn)用一次Dijkstra，1000的數(shù)據(jù)量，無(wú)情的超時(shí)了。看網(wǎng)上大神們的代碼，發(fā)現(xiàn)用兩遍Dijkstra就行了，第一遍是求出從目的地X出發(fā)，到達(dá)其余點(diǎn)的時(shí)間，第二遍還是從X出發(fā)，不過(guò)要把所有邊反向使用。把每個(gè)節(jié)點(diǎn)兩次的時(shí)間加一起，求出最大的那個(gè)即可。
代碼如下：
#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
小鼠標(biāo) 閱讀(230)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
圖論