質問編集履歴
2
コード追加
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -57,8 +57,103 @@
|
|
|
57
57
|
|
|
58
58
|
知恵を貸していただけませんか。
|
|
59
59
|
|
|
60
|
+
```C
|
|
61
|
+
#include <stdio.h>
|
|
62
|
+
#include <stdbool.h>
|
|
63
|
+
#define N 7 //配列の大きさをどう決めればいいのかわからないので7つにしました。
|
|
64
|
+
|
|
65
|
+
int main()
|
|
66
|
+
{
|
|
67
|
+
char c;
|
|
68
|
+
int e,f,x,y,w,Distance[N][N];
|
|
69
|
+
while(1)
|
|
70
|
+
{
|
|
71
|
+
|
|
72
|
+
scanf("%c %d %d", &c, &e, &f) ;
|
|
73
|
+
|
|
74
|
+
for (int i = 0; i < f; i++)
|
|
75
|
+
{
|
|
76
|
+
scanf("%d %d %d", &x, &y, &w);
|
|
77
|
+
Distance[x][y] = w;
|
|
78
|
+
}
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
}
|
|
82
|
+
|
|
83
|
+
int nPoint=N;/* 地点の数 */
|
|
84
|
+
int sp;/* 出発地の地点番号 */
|
|
85
|
+
int dp;/* 目的地の地点番号 */
|
|
86
|
+
|
|
87
|
+
scanf("%d",&sp);//出発地
|
|
88
|
+
|
|
89
|
+
scanf("%d",&dp);//目的地
|
|
90
|
+
|
|
91
|
+
int sRoute[nPoint];/* 出発地から目的地までの最短経路上の地点の地点番号を目的地から出発地の順に設定する1次元配列 */
|
|
92
|
+
int sDist;/* 出発地から目的地までの最短距離 */
|
|
93
|
+
|
|
94
|
+
int pDist[nPoint];/* 出発地から各地点までの最短距離を設定する配列 */
|
|
95
|
+
int pRoute[nPoint];
|
|
96
|
+
bool pFixed[nPoint];/* 出発地から各地点までの最短距離が確定しているかどうかを識別するための配列 */
|
|
97
|
+
int sPoint,i,j,newDist;
|
|
98
|
+
|
|
99
|
+
sDist=99999; /* 出発地から目的地までの最短距離に初期値を格納する（変更しなくてよい） */
|
|
100
|
+
|
|
101
|
+
for(i=0;i<nPoint;i++){
|
|
102
|
+
sRoute[i]=-1; /* 最短経路上の地点の地点番号に初期値を格納する */
|
|
103
|
+
pDist[i]=99999; /* 出発地から各地点までの最短距離に初期値を格納する */
|
|
104
|
+
pFixed[i]=false; /* 各地点の最短距離の確定状態に初期値を格納する */
|
|
105
|
+
}
|
|
106
|
+
|
|
107
|
+
pDist[sp-1]=0;/* 出発地から出発地自体への最短距離に0を設定する */
|
|
108
|
+
|
|
109
|
+
while(true){ /* 最短経路探索処理 */
|
|
110
|
+
i=0;
|
|
111
|
+
while(i<nPoint){/* 未確定の地点を1つ探す */
|
|
112
|
+
if(pFixed[i]==0){
|
|
113
|
+
break; /* 再内側の繰り返しから抜ける */
|
|
114
|
+
}
|
|
115
|
+
i=i+1;
|
|
116
|
+
}
|
|
117
|
+
|
|
118
|
+
if(i==nPoint){ /* 出発地から全ての地点までの最短経路が確定していれば */
|
|
119
|
+
break; /* 最短経路探索処理を抜ける */
|
|
120
|
+
}
|
|
121
|
+
|
|
122
|
+
for(j=i+1;j<nPoint;j++){ /* 最短距離がより短い地点を探す */
|
|
123
|
+
if((pFixed[j]==0) && (pDist[j] < pDist[i])){
|
|
124
|
+
i=j;
|
|
125
|
+
}
|
|
126
|
+
}
|
|
127
|
+
|
|
128
|
+
sPoint=i;
|
|
129
|
+
pFixed[sPoint]=true; /* 出発地からの最短距離を確定する */
|
|
130
|
+
|
|
131
|
+
for(j=0;j<nPoint;j++){
|
|
132
|
+
if((Distance[sPoint][j]>0) && (pFixed[j]==0)){
|
|
133
|
+
newDist=pDist[sPoint]+Distance[sPoint][j];
|
|
134
|
+
if(newDist<pDist[j]){
|
|
135
|
+
pDist[j]=newDist;
|
|
136
|
+
pRoute[j]=sPoint;
|
|
137
|
+
}
|
|
138
|
+
}
|
|
139
|
+
}
|
|
140
|
+
}
|
|
141
|
+
|
|
142
|
+
sDist=pDist[dp-1];
|
|
143
|
+
j=0;
|
|
144
|
+
i=dp-1;
|
|
145
|
+
while(i!=sp-1){
|
|
146
|
+
sRoute[j]=i;
|
|
147
|
+
i=pRoute[i];
|
|
148
|
+
j=j+1;
|
|
149
|
+
}
|
|
150
|
+
sRoute[j]=sp-1;
|
|
151
|
+
|
|
152
|
+
printf("%d",sDist);//出発地から目的地までの最短時間
|
|
153
|
+
return 0;
|
|
154
|
+
}
|
|
155
|
+
```
|
|
156
|
+
参考コード
|
|
157
|
+
[最短経路問題](https://gist.github.com/KUKDfhia/ef142e1ce3d230e8dff1ac831dfb1c90)
|
|
60
158
|
|
|
61
159
|
|
|
62
|
-
|
|
63
|
-
|
|
64
|
-
|
1
edge＝乗り換え時間、
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
バスから地下鉄の乗り換え時間
|
|
1
|
+
バスから地下鉄の乗り換え時間を付け足すコードが書けない。EOFは複数回使用してもいいのか
|
test
CHANGED
|
@@ -48,7 +48,7 @@
|
|
|
48
48
|
|
|
49
49
|
|
|
50
50
|
わかっていること
|
|
51
|
-
最短経路問題のアルゴリズムを利用する。
|
|
51
|
+
最短経路問題(グラフ)のアルゴリズムを利用する。
|
|
52
52
|
|
|
53
53
|
解決できない点
|
|
54
54
|
バスから地下鉄の乗り換え時間のedgeを付け足すコードが書けない。
|