7-10 旅游规划(25 分)
有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。
输入格式:
输入说明:输入数据的第1行给出4个正整数N、M、S、D,其中N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N−1);M是高速公路的条数;S是出发地的城市编号;D是目的地的城市编号。随后的M行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。
输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
#include<bits/stdc++.h> using namespace std; #define maxn 0x7fffffff int mat[505][505],vis[505],pay[505][505]; /* mat 是图的邻接矩阵表示,vis是标记数组 , pay 是花费的邻接矩阵表示 */ int dis[505],cost[505],n,m,path[505]; //最短路 + 路径输出 //n 是点的个数 标记为 0 ~ n-1 , //dis 最短路记录数组,cost 最小花费记录数组,path 路径记录数组 void dijkstra(int s) //修改后的最短路算法,+path 记录 和 花费计算 { int i,j; memset(vis,0,sizeof(vis));//清空标记数组 for(i=0;i<n;i++) { /* 用mat临接矩阵的值初始化dis 的值 用pay临接矩阵的值初始化cost 的值 */ dis[i]=mat[s][i]; cost[i]=pay[s][i]; if(dis[i]!=maxn) //无穷大代表此路不通 path[i] =-1,否则就在路径加入这个点 path[i]=s; else path[i]=-1; } vis[s]=1;//起始点标记 dis[s]=0;//自己到自己的花费cost = 0 cost[s]=0; for(i=1;i<n;i++) { int k=s,u=maxn; /* 找出到s距离最短&没标记的点,作为中转点更新dis值 */ for(j=0;j<n;j++) { if(!vis[j]&&dis[j]<u) { u=dis[j]; k=j; } } vis[k]=1;//标记这个点 for(j=0;j<n;j++) { if(!vis[j]&&mat[k][j]!=maxn) { /* 用这个点更新dis值,cost 和 dis同步更新,参数值相同 如果把k作为中转点成功缩减了dis值,就让k点加入path路径里 */ if(dis[j]>dis[k]+mat[k][j]) { dis[j]=dis[k]+mat[k][j]; cost[j]=cost[k]+pay[k][j]; path[j]=k; } /* 最短路径dis相同的话,选择花费最少的,最小cost */ else if(dis[j]==dis[k]+mat[k][j]) { /* 如果这个花费更加优,那么把这个点加入,更新最优秀的路径 最后path里面记录的是最优路径 */ if(cost[j]>cost[k]+pay[k][j]) { cost[j]=cost[k]+pay[k][j]; path[j]=k; } } } } } } void print(int s,int t) { stack<int>q; /* 从path里溯源t = path[t],返回上一个和t联通的路径,由后往前,把s~t路径放入队列里面,然后输出 */ while(t!=s) { q.push(t); t=path[t]; } q.push(t); while(!q.empty()) { cout<<q.top()<<" "; q.pop(); } } int main() { int s,t,a,b,d,w,i,j; cin>>n>>m>>s>>t; for(i=0;i<n;i++) for(j=0;j<n;j++) mat[i][j]=pay[i][j]=maxn; /* 初始化数组,让距离邻接矩阵数组值 = 无穷大,花费邻接矩阵的值 = 无穷大 这个计算方式对无向图和有向图同样适用,只需要部分修改 */ for(i=0;i<m;i++) { cin>>a>>b>>d>>w; if(mat[a][b]>d) { mat[a][b]=mat[b][a]=d; pay[a][b]=pay[b][a]=w; } else if(mat[a][b]==d) { if(pay[a][b]>w) pay[a][b]=pay[b][a]=w; } // 输入进行处理,最短路 } dijkstra(s); // 寻找从 s 开始 单源最短路 // print(s,t);// 输出路径, S 到 T 的路径 cout<<dis[t]<<" "<<cost[t]<<endl; // dist 指的是 距离 dis[t] 指的是花费 return 0; }