1111 online map (30 points)

The main idea of the topic ： shortest path ！ Given n A little bit ,m side , It may be undirected , It may be a directed edge , Give the distance between two points , Time , Finally, give the starting point and ending point , Find the shortest path from the starting point to the end point and the fastest arrival path .

Shortest path ： If the shortest path is not unique , The same shortest path takes the fastest path .

The fastest way to reach ： If the fastest path to reach is not unique , Output the path through the least points .

If the path is the same, output Distance = D; Time = T: source -> u1 -> ... -> destination

If not equal, output

Distance = D: source -> v1 -> ... -> destination

Time = T: source -> w1 -> ... -> destination

Run the shortest way twice , But there is no need to write two dijkstra, Write a dijkstra Judge which one you want by passing parameters .

Plain version , And heap optimization .

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 260010;
int e[N],ne[N],w[N],ti[N],h[N],dist[N],fast[N],path[N],idx;
bool st[N];
int n,m,s1,s2;
void add(int a,int b,int c,int d)
{
	e[idx] = b,ne[idx] = h[a],w[idx] = c,ti[idx] = d,h[a] = idx ++;
}
string pa,pb;
void dfs(int u,string &p)// Take the path 
{
	if(path[u] == -1)
	{   
		p += to_string(u);return ;
	}
	dfs(path[u],p);
	p = p + " -> " + to_string(u) ;
}
void dijkstra(int w1[],int w2[],int flag)
{
	memset(dist,0x3f,sizeof dist);
	memset(fast,0x3f,sizeof fast);
	memset(st,false,sizeof st);
	dist[s1] = 0,fast[s1] = 0;
	priority_queue<PII,vector<PII>,greater<PII>> que;
	que.push({0,s1});
	path[s1] = -1;
	while(que.size())
	{
		auto t = que.top();que.pop();
		int u = t.second;
		if(st[u]) continue;
		if(u == s2) break;
		st[u] = true;
		for(int i = h[u]; ~i; i = ne[i])
		{
			int j = e[i];
			if(flag) w2[i] = 1;// Finding the shortest time requires set points 
			if(!st[j] && dist[j] > dist[u] + w1[i])
			{
				dist[j] = dist[u] + w1[i];//0. shortest path 1. The shortest time 
				fast[j] = fast[u] + w2[i];//0. The shortest time 1. Path minimum point 
				path[j] = u;
				que.push({dist[j],j});
			}
			else if (dist[j] == dist[u] + w1[i] && fast[j] > fast[u] + w2[i])
			{
				fast[j]  = fast[u] + w2[i];
				path[j] = u;
			}
		}
	}
}
int main()
{
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	memset(h,-1,sizeof h);
	while(m --)
	{
		int a,b,c,d,e;
		cin >> a >> b >> c >> d >> e;
		add(a,b,d,e);
		if(!c) add(b,a,d,e);
	}
	cin >> s1 >> s2;
	dijkstra(w,ti,0);int mindist = dist[s2];dfs(s2,pa);
	dijkstra(ti,w,1);int mintime = dist[s2];dfs(s2,pb);
	if(pa == pb) printf("Distance = %d; Time = %d: %s",mindist,mintime,pa.c_str());
	else printf("Distance = %d: %s\nTime = %d: %s",mindist,pa.c_str(),mintime,pb.c_str());
	return 0;

}