1030 Travel Plan (30分) dij模板题（双关键字）
dijkstra算法原理
题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805464397627392
题意
1030旅行计划（30分）
旅行者地图给出了高速公路沿线城市之间的距离，以及每条高速公路的成本。现在你应该编写一个程序来帮助旅行者决定他/她的起始城市和目的地之间的最短路径。如果这样最短的路径不是唯一的，则应输出具有最低成本的路径，该路径保证是唯一的。
输入规格：
每个输入文件包含一个测试用例。每个事例都以包含 4 个正整数的行开头N,M,S和D哪里N (≤500） 是城市的数量（因此城市编号从 0 到N?1); M是高速公路的数量;S和D分别是起始城市和目的地城市。然后M线如下，每条提供高速公路的信息，格式为：
City1 City2 Distance Cost
其中，数字都是不超过 500 的整数，并用空格分隔。
输出规格：
对于每个测试用例，在一行中打印从起点到目的地的最短路径沿线的城市，后跟路径的总距离和总成本。数字必须用空格分隔，输出末尾不得有多余的空格。
Sample Input:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output:
0 2 3 3 40
邻接矩阵版
//复杂度O(n^2)
#include
using namespace std;
int INF=0x3f3f3f3f;
int N,M,S,D;//城市数、道路数、起点、终点
struct node{
int dist;//原点到该点距离（第一关键字）
int cost;//原点到该点花费（第二关键字）
bool flag;//是否访问过
bool operator < (const node &a) {
return (distcity[k].dist+dist[k][i] || (city[i].dist==city[k].dist+dist[k][i] && city[i].cost>city[k].cost+cost[k][i]))
{
city[i].dist=city[k].dist+dist[k][i];
city[i].cost=city[k].cost+cost[k][i];
fa[i]=k;//最短路径中i的前驱为k
}
}
}
}
int main()
{
cin>>N>>M>>S>>D;
int a,b,c,d;// a<--->b 距离c 花费d
for(int i=0;i>a>>b>>c>>d;
dist[a][b]=c; cost[a][b]=d;
dist[b][a]=c; cost[b][a]=d;
}
dijkstra();
//打印路径
stackpath;
int p=D;
while(p!=S){
path.push(p);
p=fa[p];
}
cout< 邻接表 优先队列版（屑）
#include
using namespace std;
typedef long long ll;
int N,M,S,D;
struct node{
int d,c,num;
}city[505];
struct edge{
int v,d,c;
edge(int a,int b,int c1):v(a),d(b),c(c1){}
};
vectorG[505];
bool operator < (const node x,const node y) {return x.d>y.d;}
bool visit[505];
int fa[505];
void dij()
{
for(int i=0;iQ;
Q.push(city[S]);
while(!Q.empty())
{
node t=Q.top(); Q.pop();
if(visit[t.num]) continue;
else visit[t.num]=1;
int u=t.num;
for(int i=0;icity[u].d+dis ||
(city[v].d==city[u].d+dis && city[v].c>city[u].c+cost))
{
city[v].d=city[u].d+dis;
city[v].c=city[u].c+cost;
fa[v]=u;
Q.push(city[v]);
}
}
}
}
void path()
{
stackst;
int p=D;
while(p!=S)
{
st.push(p);
p=fa[p];
}
cout<>N>>M>>S>>D;
for(int i=1;i<=M;++i)
{
int a,b,c,d; cin>>a>>b>>c>>d;
G[a].push_back(edge(b,c,d));
G[b].push_back(edge(a,c,d));
}
dij();
path();
cout<<" "<