バスから地下鉄の乗り換え時間を付け足すコードが書けない。EOFは複数回使用してもいいのか

バスと地下鉄を利用して目的地までの最短時間を求める

条件
①地下鉄からバスに乗り換える時間は5分
②バスからバスに乗り換える時間は5分
③地下鉄から地下鉄に乗り換える時間は10分
④バスから地下鉄に乗り換える時間は10分
⑤バス停あるいは地下鉄の駅の間には一線のバスと一線の地下鉄しか存在しない
⑥地下鉄とバスは全て一方向
我々は既にバスと地下鉄が通る駅の所要時間を知っていて、始発駅と終着駅も与えられています。
求めるべきは、始発駅から終着駅の最短時間です。

入力
入力は交通情報と最短経路を調べる二種類の情報を含みます。

交通情報は全ての路線のバスと地下鉄の情報を含みます。全ての路線の一行目には三つの欄があります。：英大文字のL、路線名、正の整数S(1<=S<=999),それぞれの欄の間は空白があります。もし路線名が英大文字ならば、地下鉄を表し、もし1から99の間の正の整数ならばバスを表します。整数Sはその路線には(S+1)つの駅があることを表します。全ての路線の一行目の後には、S行続き、そのS行全ての行に空白によって隔てられた三つの整数X,Y,T,1<=X≠<=1000,1<=T<=100があり、X駅(バス停)からY駅(バス停)にかかる時間はT分の時間がかかることを表します。
駅(バス停)から駅(バス停)までの最短時間を調べることが最大5回までです。最短時間は一行の入力で表ます。全ての最短時間の調査には三つの欄が含まれます。：英大文字Q,始発駅（始発バス停）、終着駅（終着バス停）、それぞれの欄の間には空白があります。最後の一行はEを入力することによって、最短時間の調査を終了します。

入力サンプル
L 36 2
1 2 5
2 3 3
L K 2
1 4 20
4 5 5
L 82 3
5 7 6
7 3 3
3 5 1
L A 1
2 4 1
Q 1 4
Q 1 7
Q 3 3
Q 5 2
E

出力
全ての調査をするごとに、必要な最短時間を出力します。もし調査の結果到達する路線がない場合は-1を返します。

出力サンプル
16
20
0
-1

わかっていること
最短経路問題(グラフ)のアルゴリズムを利用する。

解決できない点
バスから地下鉄の乗り換え時間のedgeを付け足すコードが書けない。
また、バスと地下鉄の路線を入力する際、EOFを使用するべきだろうと考えたが、EOFをコード中に2回以上使用できるのかわからない。（2回使用とすると一回で終了し（路線とその路線内の駅から駅にかかる時間の入力と）2回目のEOFの入力（通過路線の最短時間を求める行）ができない）
EOFを複数回使用できず最後の行のEで終わるとしたら、EOFは使わないで、whileやforループを使うべきですが、Eを入力してどうbreakにできるか解決策が自分では思い浮かびません。

知恵を貸していただけませんか。

C
1#include <stdio.h>
2#include <stdbool.h>
3#define N 7　//配列の大きさをどう決めればいいのかわからないので7つにしました。
4
5int main()
6{
7  char c;
8  int e,f,x,y,w,Distance[N][N];
9  while(1)
10    {    
11        
12        scanf("%c %d %d", &c, &e, &f) ;
13        
14        for (int i = 0; i < f; i++)    
15        {    
16            scanf("%d %d %d", &x, &y, &w);     
17            Distance[x][y] = w;    
18        }   
19    
20        
21    }
22
23  int nPoint=N;/* 地点の数 */
24  int sp;/* 出発地の地点番号 */
25  int dp;/* 目的地の地点番号 */
26  
27  scanf("%d",&sp);//出発地
28  
29  scanf("%d",&dp);//目的地
30 
31  int sRoute[nPoint];/* 出発地から目的地までの最短経路上の地点の地点番号を目的地から出発地の順に設定する1次元配列 */
32  int sDist;/* 出発地から目的地までの最短距離 */
33  
34  int pDist[nPoint];/* 出発地から各地点までの最短距離を設定する配列 */
35  int pRoute[nPoint];
36  bool pFixed[nPoint];/* 出発地から各地点までの最短距離が確定しているかどうかを識別するための配列 */
37  int sPoint,i,j,newDist;
38  
39  sDist=99999; /* 出発地から目的地までの最短距離に初期値を格納する（変更しなくてよい） */
40  
41  for(i=0;i<nPoint;i++){
42    sRoute[i]=-1; /* 最短経路上の地点の地点番号に初期値を格納する */
43    pDist[i]=99999; /* 出発地から各地点までの最短距離に初期値を格納する */
44    pFixed[i]=false; /* 各地点の最短距離の確定状態に初期値を格納する */
45  }
46  
47  pDist[sp-1]=0;/* 出発地から出発地自体への最短距離に0を設定する */
48  
49  while(true){ /* 最短経路探索処理 */
50    i=0;
51    while(i<nPoint){/* 未確定の地点を1つ探す */
52      if(pFixed[i]==0){
53        break; /* 再内側の繰り返しから抜ける */
54      }
55      i=i+1;
56    }
57    
58    if(i==nPoint){ /* 出発地から全ての地点までの最短経路が確定していれば */
59      break; /* 最短経路探索処理を抜ける */
60    }
61    
62    for(j=i+1;j<nPoint;j++){ /* 最短距離がより短い地点を探す */
63      if((pFixed[j]==0) && (pDist[j] < pDist[i])){
64        i=j;
65      }
66    }
67    
68    sPoint=i;
69    pFixed[sPoint]=true; /* 出発地からの最短距離を確定する */
70    
71    for(j=0;j<nPoint;j++){
72      if((Distance[sPoint][j]>0) && (pFixed[j]==0)){
73        newDist=pDist[sPoint]+Distance[sPoint][j];
74        if(newDist<pDist[j]){
75          pDist[j]=newDist;
76          pRoute[j]=sPoint;
77        }
78      }
79    }
80  }
81  
82  sDist=pDist[dp-1];
83  j=0;
84  i=dp-1;
85  while(i!=sp-1){
86    sRoute[j]=i;
87    i=pRoute[i];
88    j=j+1;
89  }
90  sRoute[j]=sp-1;
91  
92  printf("%d",sDist);//出発地から目的地までの最短時間
93  return 0;
94}

参考コード
最短経路問題

jimbe

2022/06/23 17:56 編集

お作りになったコードをご提示頂いて、そのコードはどこまで出来ていてどこが分からないのかという風に説明頂くほうが良いように思います。で、 edge とは何でしょうか。

行動規範の内容に同意します

回答2件

問題文を見る限り
入力終わりは文字'E'でしかないので、'E'が入力されたら、素直にbreakすればいいだけだと思います。
EOFは関係ないでしょう。
路線名にEが入力される可能性がというならば別ですが、問題としてそれは無いのでしょう。

入力例をもとに実際にグラフを作ってみましたか？
それを見て参考にしている最短経路の例を見て整理しましょう。

また、
出発点X、到着点Y、時間Tなので
Graph[X]の中に、到着点Yと時間Tをもつようにするのが、おそらく求めているEdgeでしょう。

投稿2022/06/24 00:56

ardin

総合スコア546

ご提示の問題に EOF とは一言も出ていませんので、複数回使用も何も、 EOF は関係無いものと思います。
素直に ”E" が現れるまで読み込むように作るべきと考えます。

乗り換え時間に付きましては、その判断材料になるはずの変数 e を捨ててしまっているので、これをどう保存するかを決める必要があります。
Distance が i - j 間の時間数を保持しますので、 Distance を構造体化し、時間数と共に e を持たせるのが妥当と思います。
そのうえで、 Distance の時間数を足す処理で"直前に乗っていた路線"と比較して乗り換え時間を算出し、時間数に足すことになるのではないでしょうか。
(ですので、時間数の合計を保持する側も"最後に乗っていた路線"を保持する必要があります。)

ついでに。