題意：

TT 從家里出發，準備乘坐貓貓快線前往喵星機場。貓貓快線分為經濟線和商業線兩種，它們的速度與價錢都不同。當然啦，商業線要比經濟線貴，TT 平常只能坐經濟線，但是今天 TT 的魔法貓變出了一張商業線車票，可以坐一站商業線。假設 TT 換乘的時間忽略不計，請你幫 TT 找到一條去喵星機場最快的線路，不然就要誤機了！
輸入包含多組數據。每組數據第一行為 3 個整數 N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即貓貓快線中的車站總數，起點和終點（即喵星機場所在站）編號。
下一行包含一個整數 M (1 ≤ M ≤ 1000)，即經濟線的路段條數。
接下來有 M 行，每行 3 個整數 X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐經濟線在車站 X 和車站 Y 之間往返，其中單程需要 Z 分鐘。
下一行為商業線的路段條數 K (1 ≤ K ≤ 1000)。
接下來 K 行是商業線路段的描述，格式同經濟線。
所有路段都是雙向的，但有可能必須使用商業車票才能到達機場。保證最優解唯一。
對于每組數據，輸出3行。第一行按訪問順序給出 TT 經過的各個車站（包括起點和終點），第二行是 TT 換乘商業線的車站編號（如果沒有使用商業線車票，輸出"Ticket Not Used"，不含引號），第三行是 TT 前往喵星機場花費的總時間。
本題不忽略多余的空格和制表符，且每一組答案間要輸出一個換行。

---

思路：

題目給定了起點與終點，而且要求商業線最多乘坐一次。可以枚舉每一條商業線(u,v)，計算起點s到u的最短路以及v到終點e的最短路再加上該商業線所花費的時間，然后取最短時間與不走商業線的時間進行比較，取較小值。
用dijkstra來實現：以起點s為源點求最短路，得到dis1數組，再以終點e為源點求最短路，得到dis2數組。枚舉商業線(u,v,w)，取min{dis1[u]+dis2[v]+w,dis1[v]+dis2[u]+w}，最終再與不走商業線的答案取min。
存經濟線使用了鏈式前向星，防止用鄰接矩陣導致TE。而商業線只需要存儲u,v,w即可，所以用了邊來存儲。
dijkstra：很正常的dijkstra，唯一不同就是要用pre數組來存儲每個點的上一個頂點，用于輸出時回溯路徑。
經過兩次dijkstra求最短路后，要枚舉商業線求最小時間，此時用syU和syV來表示最小時間對應的商業線頂點。枚舉完商業線后要進行輸出。輸出分為從后往前輸出（從syU到起點s）和從前往后輸出（從syV到終點e），前者使用了遞歸回溯路徑實現輸出，后者遍歷pre數組完成輸出。

---

總結：

一道兩遍dijkstra的題目，很容易T，還卡輸出格式，還多組數據。交了19發才A了。
代碼修改的地方：讀入由cin（沒關流同步）到scanf（但改完還是T了）；鏈式前向星存經濟線的數組由1100開到了2100（一開始開小了，1000的邊存兩次是2000,1100是不夠的，但開小了是TE而不是RE就想不通為什么，這個地方調了好久）；枚舉商業線的地方又換了一種寫法（但還是不知道前一種寫法哪里錯了）；最后PE又改了輸出格式，最后一組數據不用再輸出空行。
其實還有思路二：跑一次dijkstra變形，記錄答案dis[u][0/1]，其中dis[u][0]表示從起點到終點u沒有經過商業線時的最短路，在松弛的時候可以選擇商業線或者經濟線；dis[u][1]表示從起點到終點u經過商業線后的最短路，在松弛的時候只能選擇經濟線。
一開始覺得思路二只需要改一改dijkstra就能寫完，感覺很簡單就先寫的思路二。結果調了好久還是T，就轉為思路一了，而思路一也是寫了好長時間才搞定。看看其他大佬交了一兩發就A了，看來自己寫代碼的路還很長啊。

---

代碼：

#include <iostream> #include <stdio.h> #include <queue> #include <stack> using namespace std;int MAX_G=1e8; int n,s,e,m,k; //鏈式前向星 struct edge {int to,next,w; }; edge ed[2100]; int head[600],tot; void add(int x,int y,int w) {ed[++tot].to=y,ed[tot].next=head[x];ed[tot].w=w,head[x]=tot; } //邊,用于存儲商業線 struct shangye {int u,v,w; } syEdge[1100]; int dis1[600],dis2[600]; //距離起點和終點的距離 int pre1[600],pre2[600]; bool vis1[600],vis2[600]; struct point //記錄頂點v到源點的距離 {int v,juli;point(int v1,int juli1){v=v1,juli=juli1;} }; struct cmp {bool operator () (point a,point b){return a.juli>b.juli;} }; priority_queue<point,vector<point>,cmp> q; void dijkstra(int source,int dis[],int pre[],bool vis[]) {while(!q.empty())q.pop();dis[source]=0;point thePoint(source,0);q.push(thePoint);while(!q.empty()){int x=q.top().v;q.pop();if(vis[x])continue;vis[x]=1;for(int i=head[x]; i!=0; i=ed[i].next) //經濟線{int y=ed[i].to,w=ed[i].w;if(dis[y]>dis[x]+w){dis[y]=dis[x]+w;pre[y]=x;point pp(y,dis[y]);q.push(pp);}}} } void output1(int v) //從后往前輸出 {if(v!=s)output1(pre1[v]);if(v==s)printf("%d",v);elseprintf(" %d",v); } void output2(int v) //從前往后輸出 {while(v!=e){printf(" %d",v);v=pre2[v];}printf(" %d",v); } int main() {int sjzs=0; //數據組數while(~scanf("%d%d%d",&n,&s,&e)){//清空表for(int i=0; i<600; i++)head[i]=0,dis1[i]=MAX_G,dis2[i]=MAX_G,pre1[i]=0,pre2[i]=0,vis1[i]=0,vis2[i]=0;tot=0;scanf("%d",&m);//讀入for(int i=0; i<m; i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}scanf("%d",&k);for(int i=1; i<=k; i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);syEdge[i].u=x,syEdge[i].v=y,syEdge[i].w=z;}dijkstra(s,dis1,pre1,vis1);dijkstra(e,dis2,pre2,vis2);sjzs++;if(sjzs>1) cout<<endl;int minAns=MAX_G;int syU,syV; //syU連接起點s,syV連接終點e for(int i=1; i<=k; i++){int u=syEdge[i].u,v=syEdge[i].v,w=syEdge[i].w;if(minAns>min(dis1[u]+dis2[v]+w,dis1[v]+dis2[u]+w)){if(dis1[u]+dis2[v]+w<dis2[u]+dis1[v]+w){minAns=dis1[u]+dis2[v]+w;syU=u,syV=v;}else{minAns=dis1[v]+dis2[u]+w;syU=v,syV=u;}}}if(minAns>dis1[e]) //經濟線{minAns=dis1[e];output1(e);printf("\n");printf("Ticket Not Used\n");printf("%d\n",minAns);}else //含商業線syU,syV{output1(syU);output2(syV);printf("\n");printf("%d\n",syU);printf("%d\n",minAns);}} }

總結

以上是生活随笔為你收集整理的【Week7作业 B】TT的旅行日记【dijkstra】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。