PAT Emergency
9111 단어 merge
아니면 dijkstra 알고리즘이 약간 변형된 건지 길이가 같을 때 인원수와 경로 개수를 업데이트하는 건지.
마지막으로 출력된 것은 가장 짧은 경로의 개수입니다. 개수입니다.
AC 코드
1 #include <stdio.h>
2 #define MAX 1000000
3
4 int N,M,S,D;
5 int g[500][500];
6 int dis[500];
7 int cost[500];
8 int cost1[500];
9 int flag[500];
10 int path[500];
11 void Dijkstra(int v)
12 {
13 int min,i,j,pos;
14 cost[v]=cost1[v];
15 path[v]=1;
16 dis[v]=0;
17 for(i=0;i<N;i++)
18 {
19 min=MAX;
20 for(j=0;j<N;j++)
21 {
22 if(flag[j]!=1 && dis[j]<min)
23 {
24 min=dis[j];
25 pos=j;
26 }
27 }
28 flag[pos]=1;
29 for(j=0;j<N;j++)
30 {
31 if(flag[j]!=1)
32 {
33 if(dis[pos]+g[pos][j]<dis[j])
34 {
35 dis[j]=dis[pos]+g[pos][j];
36 cost[j]=cost[pos]+cost1[j];
37 path[j]=path[pos];
38 }
39 else if(dis[pos]+g[pos][j]==dis[j] )
40 {
41 path[j] += path[pos];
42 if(cost[j]<cost[pos]+cost1[j])
43 cost[j]=cost[pos]+cost1[j];
44 }
45 }
46
47 }
48 }
49 printf("%d %d
",path[D],cost[D]);
50 }
51 main()
52 {
53 int a,b,l,c;
54 int i,j;
55 scanf("%d%d%d%d",&N,&M,&S,&D);
56 for(i=0;i<N;i++)
57 {
58 scanf("%d",&cost1[i]);
59 dis[i]=MAX;
60 for(j=0;j<N;j++)
61 g[i][j]=MAX;
62
63 }
64 for(i=0;i<M;i++)
65 {
66 scanf("%d%d%d",&a,&b,&l);
67 g[a][b]=g[b][a]=l;
68 }
69 Dijkstra(S);
70 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
github에서 conflict- 충돌 (merge했을 때의 충돌?)했을 때의 대처법 · 생각 (sourcetree)sourcetree를 사용하여 github에 로컬 폴더를 공유하려고 시도했는데 conflict 이미있는 github의 리포지토리에 로컬 폴더를 공유하려고했습니다. (리포지토리에서 복제하는 것은 아니므로 xcode에서...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.