質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

受付中

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

wanwanko
wanwanko

総合スコア6

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

2回答

0評価

0クリップ

248閲覧

投稿2022/06/23 17:39

編集2022/06/26 02:16

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

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

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

  1. 交通情報は全ての路線のバスと地下鉄の情報を含みます。全ての路線の一行目には三つの欄があります。:英大文字のL、路線名、正の整数S(1<=S<=999),それぞれの欄の間は空白があります。もし路線名が英大文字ならば、地下鉄を表し、もし1から99の間の正の整数ならばバスを表します。整数Sはその路線には(S+1)つの駅があることを表します。全ての路線の一行目の後には、S行続き、そのS行全ての行に空白によって隔てられた三つの整数X,Y,T,1<=X≠<=1000,1<=T<=100があり、X駅(バス停)からY駅(バス停)にかかる時間はT分の時間がかかることを表します。
  2. 駅(バス停)から駅(バス停)までの最短時間を調べることが最大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

#include <stdio.h> #include <stdbool.h> #define N 7 //配列の大きさをどう決めればいいのかわからないので7つにしました。 int main() { char c; int e,f,x,y,w,Distance[N][N]; while(1) { scanf("%c %d %d", &c, &e, &f) ; for (int i = 0; i < f; i++) { scanf("%d %d %d", &x, &y, &w); Distance[x][y] = w; } } int nPoint=N;/* 地点の数 */ int sp;/* 出発地の地点番号 */ int dp;/* 目的地の地点番号 */ scanf("%d",&sp);//出発地 scanf("%d",&dp);//目的地 int sRoute[nPoint];/* 出発地から目的地までの最短経路上の地点の地点番号を目的地から出発地の順に設定する1次元配列 */ int sDist;/* 出発地から目的地までの最短距離 */ int pDist[nPoint];/* 出発地から各地点までの最短距離を設定する配列 */ int pRoute[nPoint]; bool pFixed[nPoint];/* 出発地から各地点までの最短距離が確定しているかどうかを識別するための配列 */ int sPoint,i,j,newDist; sDist=99999; /* 出発地から目的地までの最短距離に初期値を格納する(変更しなくてよい) */ for(i=0;i<nPoint;i++){ sRoute[i]=-1; /* 最短経路上の地点の地点番号に初期値を格納する */ pDist[i]=99999; /* 出発地から各地点までの最短距離に初期値を格納する */ pFixed[i]=false; /* 各地点の最短距離の確定状態に初期値を格納する */ } pDist[sp-1]=0;/* 出発地から出発地自体への最短距離に0を設定する */ while(true){ /* 最短経路探索処理 */ i=0; while(i<nPoint){/* 未確定の地点を1つ探す */ if(pFixed[i]==0){ break; /* 再内側の繰り返しから抜ける */ } i=i+1; } if(i==nPoint){ /* 出発地から全ての地点までの最短経路が確定していれば */ break; /* 最短経路探索処理を抜ける */ } for(j=i+1;j<nPoint;j++){ /* 最短距離がより短い地点を探す */ if((pFixed[j]==0) && (pDist[j] < pDist[i])){ i=j; } } sPoint=i; pFixed[sPoint]=true; /* 出発地からの最短距離を確定する */ for(j=0;j<nPoint;j++){ if((Distance[sPoint][j]>0) && (pFixed[j]==0)){ newDist=pDist[sPoint]+Distance[sPoint][j]; if(newDist<pDist[j]){ pDist[j]=newDist; pRoute[j]=sPoint; } } } } sDist=pDist[dp-1]; j=0; i=dp-1; while(i!=sp-1){ sRoute[j]=i; i=pRoute[i]; j=j+1; } sRoute[j]=sp-1; printf("%d",sDist);//出発地から目的地までの最短時間 return 0; }

参考コード
最短経路問題

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

jimbe

2022/06/23 17:56 編集

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

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。