POJ 3268 dijkstra() 정반대 행렬
Silver Cow Party
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 7988
Accepted: 3538
Description
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.
Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.
Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?
Input
Line 1: Three space-separated integers, respectively:
N,
M, and
X
Lines 2..
M+1: Line
i+1 describes road
i with three space-separated integers:
Ai,
Bi, and
Ti. The described road runs from farm
Ai to farm
Bi, requiring
Ti time units to traverse.
Output
Line 1: One integer: the maximum of time any one cow must walk.
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
ac 코드:#include <iostream>
#include <cstdio>
#include <string.h>
const int N=1010;
int nfarm,npath,pos;
int map1[N][N],map2[N][N],visted[N];
int dis1[N],dis2[N];
#define MAX 0x7fffffff
void dijkstra(int dis[N],int map[N][N]){
memset(visted,0,sizeof(visted));
for(int i=1;i<=nfarm;++i)
dis[i]=map[pos][i];
dis[pos]=0;
visted[pos]=1;
int newpos=pos;
for(int i=1;i<=nfarm;++i){
for(int j=1;j<=nfarm;++j){
if(!visted[j]&&map[newpos][j]!=MAX&&dis[newpos]+map[newpos][j]<dis[j]){
dis[j]=dis[newpos]+map[newpos][j];
}
}
int mmin=MAX;
for(int j=1;j<=nfarm;++j){
if(!visted[j]&&mmin>dis[j]){
mmin=dis[j];
newpos=j;
}
}
visted[newpos]=1;
}
}
int main(){
//freopen("11.txt","r",stdin);
while(~scanf("%d%d%d",&nfarm,&npath,&pos)){
int x,y,z;
for(int i=0;i<=nfarm;++i){
for(int j=0;j<=nfarm;++j){
map1[i][j]=MAX;
map2[i][j]=MAX;
}
}
while(npath--){
scanf("%d%d%d",&x,&y,&z);
map1[x][y]=z;
map2[y][x]=z;
}
dijkstra(dis1,map1);
dijkstra(dis2,map2);
int mmax=0;
/* for(int i=1;i<=nfarm;++i){
printf("%d ",dis1[i]);
}*/
for(int i=1;i<=nfarm;++i){
if(dis1[i]+dis2[i]>mmax)
mmax=dis1[i]+dis2[i];
}
printf("%d
",mmax);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.