PTA 旅游大巴（UVa 11374 机场快线）Floyd+枚举+路径打印

在W市中，旅游大巴是市民从市内去景区A的首选交通工具。旅游大巴分为普通线和快速线两种，线路、速度和价钱都不同。你有一张快速线车票，可以坐一站快速线，而其他时候只能乘坐普通线。假设换乘时间忽略不计，你的任务是找一条去景点A最快的线路。

输入格式：

输入含多组数据。每组数据第一行为3个整数N,S和E(2≤N≤500,1≤S,E≤100),即旅游大巴中的停靠站总数，起点和终点（即景点A所在站）编号。下一行包含一个整数M(1≤M≤1000)，即普通线的路段条数。以下M行每行3个整数X,Y,Z(1≤X,Y≤N,1≤Z≤100)，表示可以乘坐普通线在站点X和站点Y之间往返，其中单程需要Z分钟。下一行为快速线的路段条数K(1≤K≤1000)，以下K行是这些路段的描述，格式同普通线。所有路段都是双向的，但有可能必须使用快速车票才能到达景点A。保证最优解唯一。

输出格式：

对于每组数据，输出3行。第一行按访问顺序给出经过的各个站点（包括起点和终点），第二行是换乘快速线的车站编号(如果没有快速线车票，输出Ticket Not Used),第三行是总时间。

注意：输出时，每两组数据之间要加一个空行。并且不会过滤行末空格。

输入样例:

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

思路：因为站点只有500，那就偷懒跑个弗洛伊德先。同时，快速线只有一条，所以对普通线路跑完最短路之后，任意两点的耗时就可以打表查询。

然后枚举商业线的加入，是否能够使得原有结果更加快。

坑点：PTA上是多组输入，并且每组输出之间还要加空格，可能会存在重边?

AC代码：

#include
using namespace std;
#define INF 0x3f3f3f3f
int mp[505][505];//存储耗时
int path[505][505];//存储路径，用于打印
int main(){int tmd,n,s,e,a,b,c,cc=0;while(cin>>n>>s>>e){//初始化，默认全部不跑通memset(mp,0x3f3f3f3f,sizeof mp);memset(path,-1,sizeof mp);for(int i=0;i<=n;i++)mp[i][i]=0;int m;cin>>m;for(int i=0;i>a>>b>>c;//建立双向边mp[a][b]=min(mp[a][b],c);mp[b][a]=min(mp[b][a],c);}//每组输出之间加空格if(cc!=0)cout<=0x3f3f3f3f){path[i][j] = -1;}else{path[i][j] = j;}}}//弗洛伊德模板for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j] > mp[i][k]+mp[k][j]){mp[i][j] = mp[i][k]+mp[k][j];//如果能使得路更短，更新path[i][j] = path[i][k];}}}}int k,ans_tim=mp[s][e],ans_huan=-1,ans_hu=-1;cin>>k;for(int i=0;i>a>>b>>c;//枚举每一条快速线的加入能否使得结果更好if(mp[s][a] + mp[b][e]<=0x3f3f3f3f){if(mp[s][a] + mp[b][e]+c < ans_tim){ans_tim  =mp[s][a] + mp[b][e]+c ;ans_huan = a;ans_hu =b;}}}if(ans_huan!=-1){//用到快速线路//起点-》快速站起点-》快速站终点-》终点tmd=s;int f=0;while(tmd!= ans_huan){if(f!=0)cout<<" ";f=1;cout<

#include
using namespace std;
int cnt =0;
int n,s,t;
int head[100086];
int dis1[100086];
int dis2[100086];
int vis[100086];
vectorans;
struct TT{int to;int val;int next;
}edge[200086];
void add(int u,int v,int c){cnt ++;edge[cnt].next = head[u];head[u]=cnt;edge[cnt].to =v ;edge[cnt].val = c;
}
struct T{int id;int c;bool operator < (const T &x) const{return c > x.c;}
};
void dij(int x,int dis[]){priority_queueq;q.push({x,0});dis[x]=0;while(!q.empty()){int now = q.top().id;q.pop();vis[now]=1;for(int u= head[now];u!=-1;u = edge[u].next){int v  =edge[u].to;if(vis[v]==0 && dis[v]>dis[now]+edge[u].val){dis[v] = dis[now]+edge[u].val;q.push({v,dis[v]});}}}}
int main(){while(cin>>n>>s>>t){memset(vis,0,sizeof vis);memset(head,-1,sizeof head);memset(dis1,63,sizeof dis1);memset(dis2,63,sizeof dis2);int m;cin>>m;for(int i=0;i>a>>b>>c;add(a,b,c);add(b,a,c);}dij(s,dis1);memset(vis,0,sizeof vis);dij(t,dis2);int k;cin>>k;int kc =0;int ans = dis1[t];for(int i=1;i<=k;i++){int a,b,c;cin>>a>>b>>c;if(dis1[a] + dis2[b]+c < ans){ans = dis1[a] + dis2[b]+c;kc=a;}if(dis1[b] + dis2[a]+c < ans){ans = dis1[b] + dis2[a]+c;kc=b;}	}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！