layout: post
title: 训练指南 UVA - 11374(最短路Dijkstra + 记录路径 + 模板)
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 最短路
- Dijkstra
- 图论
- 训练指南
Airport Express
题意
机场快线有经济线和商业线,现在分别给出经济线和商业线的的路线,现在只能坐一站商业线,其他坐经济线,问从起点到终点的最短用时是多少,还有路线是怎样的;
题解
预处理出起点到所有站的最短距离和终点到所有站的最短距离,枚举要坐的那趟商业线,然后里面最小的就是答案了;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=550;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
int from,to,dist;
};
struct HeapNode{
int d,u;
bool operator <(const HeapNode& rhs)const{
return d>rhs.d;
}
};
struct Dijkstra{
int n,m; //点数和边数 点编号0~N-1
vector<Edge>edges;
vector<int>G[maxn];
bool done[maxn];
int d[maxn];
int p[maxn];
void init(int n){
this->n=n;
for(int i=0;i<n;i++)G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int dist){
edges.push_back((Edge){from,to,dist});
m=edges.size();
G[from].push_back(m-1);
}
void dijkstra(int s){
priority_queue<HeapNode>Q;
for(int i=0;i<n;i++)d[i]=inf;
d[s]=0;
memset(done,0,sizeof(done));
Q.push((HeapNode){0,s});
while(!Q.empty()){
HeapNode x=Q.top();Q.pop();
int u=x.u;
if(done[u])continue;
done[u]=true;
for(int i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(d[e.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;
p[e.to]=G[u][i];
Q.push((HeapNode){d[e.to],e.to});
}
}
}
}
void GetShortestPaths(int s,int* dist,vector<int>* paths){//paths是二维链表
dijkstra(s);
for(int i=0;i<n;i++){
dist[i]=d[i];
paths[i].clear();
int t=i;
paths[i].push_back(t);
while(t!=s){
paths[i].push_back(edges[p[t]].from);
t=edges[p[t]].from;
}
reverse(paths[i].begin(),paths[i].end());
}
}
};
Dijkstra solver;
int d1[maxn],d2[maxn];
vector<int>paths1[maxn],paths2[maxn];
int main()
{
// std::ios::sync_with_stdio(false);
// std::cin.tie(0);
// std::cout.tie(0);
int kase=0,N,S,E,M,K,X,Y,Z;
while(scanf("%d%d%d%d", &N, &S, &E, &M) == 4) {
solver.init(N);
S--;E--;
for(int i=0;i<M;i++){
scanf("%d%d%d", &X, &Y, &Z); X--; Y--;
solver.AddEdge(X,Y,Z);
solver.AddEdge(Y,X,Z);
}
solver.GetShortestPaths(S,d1,paths1);
solver.GetShortestPaths(E,d2,paths2);
int ans=d1[E];
vector<int>path=paths1[E];
int midpoint=-1;
scanf("%d", &K);
for(int i=0;i<K;i++){
scanf("%d%d%d", &X, &Y, &Z); X--; Y--;
for(int j=0;j<2;j++){
if(d1[X]+d2[Y]+Z<ans){
ans=d1[X]+d2[Y]+Z;
path=paths1[X];
for(int p=paths2[Y].size()-1;p>=0;p--)
path.push_back(paths2[Y][p]);
midpoint=X;
}
swap(X,Y);
}
}
if(kase != 0) printf("\n");
kase++;
for(int i = 0; i < path.size()-1; i++) printf("%d ", path[i]+1);
printf("%d\n", E+1);
if(midpoint == -1) printf("Ticket Not Used\n"); else printf("%d\n", midpoint+1);
printf("%d\n", ans);
}
return 0;
}