題目：

眾所周知，TT 有一只魔法貓。

今天他在 B 站上開啟了一次旅行直播，記錄他與魔法貓?jiān)谶餍锹糜螘r(shí)的奇遇。 TT 從家里出發(fā)，準(zhǔn)備乘坐貓貓快線前往喵星機(jī)場。貓貓快線分為經(jīng)濟(jì)線和商業(yè)線兩種，它們的速度與價(jià)錢都不同。當(dāng)然啦，商業(yè)線要比經(jīng)濟(jì)線貴，TT 平常只能坐經(jīng)濟(jì)線，但是今天 TT 的魔法貓變出了一張商業(yè)線車票，可以坐一站商業(yè)線。假設(shè) TT 換乘的時(shí)間忽略不計(jì)，請你幫 TT 找到一條去喵星機(jī)場最快的線路，不然就要誤機(jī)了！

輸入：
輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)第一行為 3 個(gè)整數(shù) N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即貓貓快線中的車站總數(shù)，起點(diǎn)和終點(diǎn)（即喵星機(jī)場所在站）編號。

下一行包含一個(gè)整數(shù) M (1 ≤ M ≤ 1000)，即經(jīng)濟(jì)線的路段條數(shù)。

接下來有 M 行，每行 3 個(gè)整數(shù) X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐經(jīng)濟(jì)線在車站 X 和車站 Y 之間往返，其中單程需要 Z 分鐘。

下一行為商業(yè)線的路段條數(shù) K (1 ≤ K ≤ 1000)。

接下來 K 行是商業(yè)線路段的描述，格式同經(jīng)濟(jì)線。

所有路段都是雙向的，但有可能必須使用商業(yè)車票才能到達(dá)機(jī)場。保證最優(yōu)解唯一。

輸出：
對于每組數(shù)據(jù)，輸出3行。第一行按訪問順序給出 TT 經(jīng)過的各個(gè)車站（包括起點(diǎn)和終點(diǎn)），第二行是 TT 換乘商業(yè)線的車站編號（如果沒有使用商業(yè)線車票，輸出"Ticket Not Used"，不含引號），第三行是 TT 前往喵星機(jī)場花費(fèi)的總時(shí)間。

本題不忽略多余的空格和制表符，且每一組答案間要輸出一個(gè)換行

樣例：
Input:

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

Output:

1 2 4 2 5

思路：

將商務(wù)線與經(jīng)濟(jì)線分開用鏈表存儲(chǔ)。
通過枚舉商務(wù)線，來確定最短路徑。設(shè)起點(diǎn)為s，終點(diǎn)為e，枚舉某條的商務(wù)線起點(diǎn)為x，終點(diǎn)為y，只需要找出min{dis1[u]+dis2[v]+w, dis1[v]+dis2[u]+w}即可，dis1數(shù)組存放了從起點(diǎn)s開始的到所有點(diǎn)的最短路徑值。dis2數(shù)組存放了從終點(diǎn)e開始的到所有點(diǎn)的最短路徑值。
需排除兩點(diǎn)不連通的情況。

代碼：

#include<iostream> #include<cstring> using namespace std; const int maxx=1000000; int n,m,k,s,e,tot,ans=maxx,head[maxx],dis1[maxx],dis2[maxx]; int pre1[maxx],pre2[maxx],p[maxx],sum,chu,a[maxx]; bool flag[maxx]; int ans_u,ans_v,ans_w; struct node {int v;int w;int next; }e1[maxx]; void add_edge(int u,int v,int w) {e1[++tot].v=v;e1[tot].w=w;e1[tot].next=head[u];head[u]=tot; } void dij1(int u) {memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++)dis1[i]=maxx;dis1[u]=0;for(int i=1;i<=n;i++){int k=0,minn=maxx;for(int j=1;j<=n;j++)if(!flag[j]&&dis1[j]<minn){minn=dis1[j];k=j;}flag[k]=1;for(int j=head[k];j;j=e1[j].next)if(!flag[e1[j].v]&&dis1[e1[j].v]>dis1[k]+e1[j].w){dis1[e1[j].v]=dis1[k]+e1[j].w;pre1[e1[j].v]=k;}} } void dij2(int u) {memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++)dis2[i]=maxx;dis2[u]=0;for(int i=1;i<=n;i++){int k=0,minn=maxx;for(int j=1;j<=n;j++)if(!flag[j]&&dis2[j]<minn){minn=dis2[j];k=j;}flag[k]=1;for(int j=head[k];j;j=e1[j].next)if(!flag[e1[j].v]&&dis2[e1[j].v]>dis2[k]+e1[j].w){dis2[e1[j].v]=dis2[k]+e1[j].w;pre2[e1[j].v]=k;}} } int main() {int x,y,z,u,v,w,T;while(scanf("%d%d%d",&n,&s,&e)!=EOF){if(T!=0) printf("\n");T++;memset(flag,0,sizeof(flag));memset(pre1,0,sizeof(pre1));memset(pre2,0,sizeof(pre2));memset(head,0,sizeof(head));memset(a,0,sizeof(a));tot=0;cin>>m;ans_u=0;sum=0;for(int i=1;i<=m;i++){cin>>x>>y>>z;add_edge(x,y,z);add_edge(y,x,z);}dij1(s);dij2(e);cin>>k;int ans=dis1[e];for(int i=1;i<=k;i++){cin>>u>>v>>w;if(dis1[u]+dis2[v]+w<ans){ans=dis1[u]+dis2[v]+w;ans_u=u;ans_v=v;}if(dis2[u]+dis1[v]+w<ans)//反向更新 {ans=dis2[u]+dis1[v]+w;ans_u=v;ans_v=u;}}int tmp;if(ans_u==0)//不需要商務(wù)線 {tmp=e;while(tmp){a[++sum]=tmp;if(tmp==s) break;tmp=pre1[tmp];}for(int i=sum;i>=2;i--) cout<<a[i]<<" ";cout<<a[1]<<endl;cout<<"Ticket Not Used"<<endl<<ans<<endl;}else//需要商務(wù)線 {tmp=ans_v;while(tmp){a[++sum]=tmp;if(tmp==e) break;tmp=pre2[tmp];}for(int i=1;i<=sum/2;i++)swap(a[i],a[sum-i+1]);tmp=ans_u;while(tmp){a[++sum]=tmp;if(tmp==s) break;tmp=pre1[tmp];}for(int i=sum;i>=2;i--) cout<<a[i]<<" ";cout<<a[1]<<endl;cout<<ans_u<<endl<<ans<<endl;}}return 0; }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。