題意：

眾所周知，TT 有一只魔法貓。
今天他在 B 站上開啟了一次旅行直播，記錄他與魔法貓在喵星旅游時的奇遇。 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 前往喵星機場花費的總時間。
本題不忽略多余的空格和制表符，且每一組答案間要輸出一個換行

樣例輸入：

4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

樣例輸出：

1 2 4
2
5

思路：

題意分析：
已知起點和終點，單源最短路問題，且沒有負邊，基本可以確定使用Dijkstra算法

Dijkstra:
關鍵操作：松弛
設置 s 為源點,𝑑𝑖𝑠[a]表示源點 s 到點 a 的最短距離, 初始化𝑑𝑖𝑠[s]=0,𝑑𝑖𝑠[i]=𝑖𝑛𝑓(無窮大), 將 s 加入最小堆，每次從堆中取出一個點 x，遍歷 x 的所有鄰接邊 (𝑥，𝑦，𝑤)，比較𝑑𝑖𝑠[y] 與𝑑𝑖𝑠[x]+𝑤的大小,若𝑑𝑖𝑠[y]>𝑑𝑖𝑠[x]+𝑤，則松弛成功。更新𝑑𝑖𝑠[y]的大小，將 y 加入最小堆中。不斷執行上述操作，直至最小堆為空，最后得到的𝑑𝑖s數組 即為所求單源最短路值 。

具體分析：
大方向上有兩種情況：使用商業線，不使用商業線
其中，使用商業線又有兩種情況：以起點為源點，以終點為源點

依次枚舉每條商業線(u, v, w)，以起點為源點求單源最短路，得到 dis1 數組，再以終點為源點求單源最短路，得到 dis2 數組 取 min{dis1[u]+dis2[v]+w, dis1[v]+dis2[u]+w}，最終再與不走商業線的答案dis[E]取min

獲得路徑：這里記錄了每個節點的前一個節點，找到最小路徑之后可以通過記錄的前一個節點依次確定線路。

這里使用鏈式前向星存儲邊，注意這是個無向圖，在插邊時要注意一下。

注意點：
本題格式上要求比較嚴格

總結：

1.Dijkstra的模板
2.容易略掉情況：起點為源點，終點為源點
3.重復使用的數組及時更新

代碼：

#include<bits/stdc++.h> using namespace std; const int inf=5*1e8;struct edge{int v,w,nxt; }G[2000]; int head[2000],tot; //tot是head的下標 void init(){tot=0;memset(head,0,sizeof(head)); }void add(int u,int v,int w){G[++tot].v=v; G[tot].w=w; G[tot].nxt=head[u];head[u]=tot; }int dis1[501],dis2[501],pre1[501],pre2[501]; //pre記錄經過節點的前一個節點 bool vis[501]; int N,S,E,M,X,Y,Z,K;struct Q{int u,w;bool operator<(const Q &q) const{if(w!=q.w) return w>q.w;} }; void dijkstra1(int s){ //起點S priority_queue<Q> q;for(int i=1;i<=N;i++) {dis1[i]=inf; vis[i]=0; pre1[i]=0;} // memset(vis,0,sizeof(vis)); // memset(pre1,-1,sizeof(pre1));q.push({s,0});dis1[s]=0;pre1[s]=-1;while(!q.empty()){int u=q.top().u;q.pop();if(vis[u]) continue; //已經遍歷過vis[u]=1;for(int i=head[u];i;i=G[i].nxt){int v=G[i].v;if(dis1[v]>dis1[u]+G[i].w){dis1[v]=dis1[u]+G[i].w; //松弛pre1[v]=u; //v前面的節點是u q.push({v,dis1[v]}); }}} }void dijkstra2(int s){ //終點E priority_queue<Q> q;for(int i=1;i<=N;i++) {dis2[i]=inf; vis[i]=0; pre2[i]=0;} // memset(vis,0,sizeof(vis)); // memset(pre2,-1,sizeof(pre2));q.push({s,0});dis2[s]=0;pre2[s]=-1;while(!q.empty()){int u=q.top().u;q.pop();if(vis[u]) continue; //已經遍歷過vis[u]=1;for(int i=head[u];i;i=G[i].nxt){int v=G[i].v;if(dis2[v]>dis2[u]+G[i].w){dis2[v]=dis2[u]+G[i].w; //松弛pre2[v]=u; //v前面的節點是u q.push({v,dis2[v]}); }}} } void thePath1(int m){ //從S向前找路徑 if(m==S){printf("%d",m); return;}thePath1(pre1[m]);printf(" %d",m); }void thePath2(int m){ //從E向后找路徑 while(m!=E){printf(" %d",m);m=pre2[m]; }printf(" %d",m); }int main(){int num=1;while(scanf("%d%d%d",&N,&S,&E)!=EOF){int b_start=-1,b_end=-1; //記錄商業線起點和終點 init();scanf("%d",&M);for(int i=0;i<M;i++){scanf("%d%d%d",&X,&Y,&Z);add(X,Y,Z);add(Y,X,Z); //加邊 }dijkstra1(S); dijkstra2(E);int ans=inf; //未使用商業線 scanf("%d",&K);for(int i=0;i<K;i++){ //枚舉商業線 scanf("%d%d%d",&X,&Y,&Z);int ans1=dis1[X]+dis2[Y]+Z; //兩種情況取最小值 int ans2=dis2[X]+dis1[Y]+Z;if(ans1<ans) {ans=ans1; b_start=X; b_end=Y;} if(ans2<ans) {ans=ans2; b_start=Y; b_end=X;} }if(num!=1) printf("\n");num++;if(dis1[E]>ans){ //使用了商業線 thePath1(b_start);thePath2(b_end);printf("\n%d\n",b_start);printf("%d\n",ans);}else{thePath1(E);printf("\nTicket Not Used\n");printf("%d\n",dis1[E]);}}return 0; }

總結

以上是生活随笔為你收集整理的TT 的旅行日记（Dijkstra)的全部內容，希望文章能夠幫你解決所遇到的問題。

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