結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2019-01-10 02:12:59 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,292 bytes |
コンパイル時間 | 221 ms |
コンパイル使用メモリ | 30,976 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-24 01:03:51 |
合計ジャッジ時間 | 1,282 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include<stdio.h> #include<stdlib.h> #define POS(i,j) ((i)*n+(j)) void run(void){ int n,m,src,dst; scanf("%d%d%d%d",&n,&m,&src,&dst); int *g=(int *)calloc(n*n,sizeof(int)); while(m--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); g[POS(a,b)]=c; g[POS(b,a)]=c; } int *dp=(int *)calloc(n,sizeof(int)); const int inf=10000*n+1; int i,j; for(i=0;i<n;i++) dp[i]=inf; dp[src]=0; int *used=(int *)calloc(n,sizeof(int)); for(i=0;i<n;i++){ for(j=0;used[j];j++); int v=j; for(;j<n;j++){ if(!used[j] && dp[j]<dp[v]){ v=j; } } used[v]=1; for(j=0;j<n;j++){ if(g[POS(v,j)]==0 || dp[j]<=dp[v]+g[POS(v,j)]) continue; dp[j]=dp[v]+g[POS(v,j)]; } } int *can=(int *)calloc(n,sizeof(int)); can[dst]=1; for(i=0;i<n;i++){ for(j=0;j<n && can[j]!=1;j++); if(j>=n) break; int v=j; can[v]=2; for(j=0;j<n;j++){ if(can[j]!=0) continue; if(g[POS(j,v)]==0) continue; if(dp[v]<dp[j]+g[POS(j,v)]) continue; can[j]=1; } } int now=src; while(now!=dst){ printf("%d ",now); for(j=0;j<n;j++){ if(can[j] && g[POS(now,j)]>0 && dp[j]==dp[now]+g[POS(now,j)]){ break; } } now=j; } printf("%d\n",now); return; } int main(void){ run(); return 0; }