結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2015-07-15 09:20:10 |
言語 | C90 (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 1,007 bytes |
コンパイル時間 | 244 ms |
コンパイル使用メモリ | 21,888 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-08 07:39:57 |
合計ジャッジ時間 | 1,202 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:25:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | scanf("%d %d %d %d", &nodeMax, &loadMax, &stPos, &goPos); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.c:28:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 28 | scanf("%d %d %d", &a, &b,&c); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h> #define VMAX (202) #define INF (99999999) int length[VMAX][VMAX]; int dis[VMAX][VMAX]; int min(int a, int b){ if(a<b){return a;} return b; } int main(void){ int i,j,k; int nodeMax, loadMax, stPos, goPos; for(i=0;i<VMAX;i++){ for(j=0;j<VMAX;j++){ length[i][j] = INF; dis[i][j] = INF; } } scanf("%d %d %d %d", &nodeMax, &loadMax, &stPos, &goPos); for(i=0;i<loadMax;i++){ int a,b,c; scanf("%d %d %d", &a, &b,&c); if( i != stPos ){ } length[a][b] = c; length[b][a] = c; dis[a][b] = c; dis[b][a] = c; } for(k=0;k<nodeMax;k++){ for(i=0;i<nodeMax;i++){ for(j=0;j<nodeMax;j++){ length[i][j] = min( length[i][j], length[i][k] + length[k][j]); } } } for(i=0;i<VMAX;i++){ length[i][i] = 0; } k = stPos; while(k != goPos){ printf("%d ", k); for(i=0;i<nodeMax;i++){ if( i == k){continue;} if( i!= k && dis[k][i] + length[i][goPos] == length[k][goPos]){ k=i; break; } } } printf("%d\n", goPos); return 0; }