明天就要考PAT,为了应付期末已经好久没有刷题了啊啊啊啊,今天开了一道最短路,状态不是很好
题目大意：给一张地图，两个结点中既有距离也有时间，有的单行有的双向，要求根据地图推荐两条路线：一条是最快到达路线，一条是最短距离的路线。
第一行给出两个整数N和M，表示地图中地点的个数和路径的条数。接下来的M行每一行给出：道路结点编号V1 道路结点编号V2 是否单行线 道路长度 所需时间
要求第一行输出最快到达时间Time和路径，第二行输出最短距离Distance和路径
就用两次dij+dfs即可,好嘛,今晚dfs也不用练了.最好明天出一道这道题
#include <iostream>
#include<bits/stdc++.h>
#define each(a,b,c) for(int a=b;a<=c;a++)
#define de(x) cout<<#x<<" "<<(x)<<endl
using namespace std;
const int maxn=500+5;
const int inf=0x3f3f3f3f;
int T[maxn][maxn];
int dis1[maxn];
int dis2[maxn];
bool vis[maxn];
int n,m,from,to;
vector<int>pre1[maxn],pre2[maxn];
/// vis =0 从0开始
struct edge
{
int v;
int length;
int time;
edge(int v,int length,int time):v(v),length(length),time(time){}
};
vector<edge>G[maxn];
struct node
{
int v;
int len;
node(int v=0,int len=0):v(v),len(len){}
bool operator<(const node&r)const
{
return len>r.len;
}
};
void dijkstra1(int start,int n)
{
for(int i=0;i<=n;i++)
{
vis[i]=false;
dis1[i]=inf;
}
dis1[start]=0;
priority_queue<node>Q;
Q.push(node(start,0));
node temp;
while(!Q.empty())
{
temp=Q.top();
Q.pop();
int u=temp.v;
if(vis[u])continue;
vis[u]=true;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i].v;
int len=G[u][i].length;
if(!vis[v]&&dis1[v]>dis1[u]+len)
{
dis1[v]=dis1[u]+len;
pre1[v].clear();
pre1[v].push_back(u);
Q.push(node(v,dis1[v]));
}
else if(!vis[v]&&dis1[v]==dis1[u]+len)
{
pre1[v].push_back(u);
}
}
}
}
void dijkstra2(int start,int n)
{
for(int i=0;i<=n;i++)
{
vis[i]=false;
dis2[i]=inf;
}
dis2[start]=0;
priority_queue<node>Q;
while(!Q.empty())Q.pop();
Q.push(node(start,0));
node temp;
while(!Q.empty())
{
temp=Q.top();
Q.pop();
int u=temp.v;
if(vis[u])continue;
vis[u]=true;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i].v;
int len=G[u][i].time;
if(!vis[v]&&dis2[v]>dis2[u]+len)
{
dis2[v]=dis2[u]+len;
pre2[v].clear();
pre2[v].push_back(u);
Q.push(node(v,dis2[v]));
}
else if(!vis[v]&&dis2[v]==dis2[u]+len)
{
pre2[v].push_back(u);
}
}
}
}
vector<int>path;
vector<int>ans_path;
vector<int>ans_path2;
int min_time=inf;
void dfs1(int v)
{
path.push_back(v);
if(v==from)
{
int temp=0;
for(int i=0;i<path.size()-1;i++)
{
temp+=T[path[i+1]][path[i]];
}
if(temp<min_time)
{
min_time=temp;///忘记更新最小值了\吐血
ans_path=path;
}
path.pop_back();
return ;
}
for(int i=0;i<pre1[v].size();i++)
{
dfs1(pre1[v][i]);
}
path.pop_back();
}
int max_n=maxn;
void dfs2(int v)
{
path.push_back(v);
if(v==from)
{
if(path.size()<max_n)
{
max_n=path.size();
ans_path2=path;
}
path.pop_back();
return;
}
for(int i=0;i<pre2[v].size();i++)
{
dfs2(pre2[v][i]);
}
path.pop_back();
}
/*
V1 V2 one-way length time
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5
*/
int main()
{
cin>>n>>m;
int v1,v2,flag,len,time;
each(i,1,m)
{
cin>>v1>>v2>>flag>>len>>time;
if(flag==1)
{
G[v1].push_back(edge(v2,len,time));
T[v1][v2]=T[v2][v1]=time;
}
else
{
G[v1].push_back(edge(v2,len,time));
G[v2].push_back(edge(v1,len,time));
T[v1][v2]=T[v2][v1]=time;
}
}
cin>>from>>to;
dijkstra1(from,n);
dijkstra2(from,n);
//de(dis1[to]);
//de(dis2[to]);
dfs1(to);
dfs2(to);
printf("Distance = %d", dis1[to]);
if(ans_path == ans_path2) {
printf("; Time = %d: ", dis2[to]);
} else {
printf(": ");
for(int i = ans_path.size() - 1; i >= 0; i--) {
printf("%d", ans_path[i]);
if(i != 0) printf(" -> ");
}
printf("\nTime = %d: ", dis2[to]);
}
for(int i = ans_path2.size() - 1; i >= 0; i--) {
printf("%d", ans_path2[i]);
if(i != 0) printf(" -> ");
}
/*
Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5
*/
}