pat 数据结构与算法题目集
题目描述
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第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
输出样例:
3 40
其实关于迪杰斯特拉算法我之前的blog https://www.cnblogs.com/liuzhaojun/p/11132220.html有详细的解释
陈越姥姥确实讲的好，这道题的难点就是一条边有两个权重，长度和花费。一个简单的邻接矩阵是无法存储的，所以
想到，用三维数组，其实不是我想到了，是我看了别人的blog，微笑脸。
/*
Name:
Copyright:
Author: 流照君
Date: data
Description:
*/
#include <iostream>
#include<string>
#include <algorithm>
#include <vector>
#define inf 1005
using namespace std;
typedef long long ll;
int n,m,s,d; //三元组
int mat[inf][inf][2],dis[inf],pay[inf],book[inf];
void Dijkstra()
{
book[s]=1;
for(int i=0;i<n;i++)
{
int min1=inf;
int flag=0;
for(int j=0;j<n;j++)//找出dis数组中未标记的最小点
{
if(dis[i]<min1&&book[i]==0)
{
min1=dis[i];
flag=i;
}
}
book[flag]=1;
for(int k=0;k<n;k++)
{
if(dis[flag]+mat[flag][k][0]<dis[k])
{
dis[k]=dis[flag]+mat[flag][k][0];
pay[k]=pay[flag]+mat[flag][k][1];
}
else if(dis[flag]+mat[flag][k][0]==dis[k]&&(pay[k]>(pay[flag]+(mat[flag][k][1]))))
{
pay[k]=pay[flag]+mat[flag][k][1];
}
}
}
}
int main(int argc, char** argv)
{
#ifdef ONLINE_JUDGE//条件编译，如果有oj则忽略文件读取
#else
//freopen("in.txt", "r", stdin);//输入输出文件重定向
//freopen("out.txt", "w", stdout);
#endif //#if, #ifdef, #ifndef这些条件命令的结束标志.
//代码位置
int x,y,l,c;
cin>>n>>m>>s>>d;
fill(mat[0][0],mat[0][0]+inf*inf*2,inf);
fill(dis,dis+inf,inf);
fill(pay,pay+inf,inf);
for(int i=0;i<n;i++)
for(int j=0;j<2;j++)
mat[i][i][j]=0;
while(m--)
{
cin>>x>>y>>l>>c;
mat[x][y][0]=l;
mat[y][x][0]=l;
mat[x][y][1]=c;
mat[y][x][1]=c;
}
for(int i=0;i<n;i++)
{
dis[i]=mat[s][i][0];
pay[i]=mat[s][i][1];
}
Dijkstra();
cout<<dis[d]<<" "<<pay[d]<<endl; //思考为什么pay[d]一定是最小的？？？
return 0;
}