题解

//思路：跑两遍Dijkstra,先找出以1和n为起点的最短路径，再遍历寻找最优的会合城市与时间
#include<bits/stdc++.h>
using namespace std;
const long long N=200001;
#define PII pair<long long,long long>
struct node{
	long long to,w;
};
long long n,m;
long long dis[N],rdis[N],ans=0x3f3f3f3f3f3f;
vector<vector<node> > a(N); 
vector<long long> s;
void dijkstra_1()
{
	fill(dis+1,dis+1+n,0x3f3f3f3f3f3f);
	bool vis[N];
	fill(vis+1,vis+1+n,0); 
	dis[1]=0;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.push({0,1});
	while(!q.empty())
	{
		long long u=q.top().second;
		long long d=q.top().first;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto cur:a[u])
		{
			long long nu=cur.to;
			long long w=cur.w;
			if(dis[u]+w<dis[nu])
			{
				dis[nu]=dis[u]+w;
				q.push({dis[nu],nu});
			}
		}
	}
}
void dijkstra_n()
{
	fill(rdis+1,rdis+1+n,0x3f3f3f3f3f3f);
	bool vis[N];
	fill(vis+1,vis+1+n,0); 
	rdis[n]=0;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.push({0,n});
	while(!q.empty())
	{
		long long u=q.top().second;
		long long d=q.top().first;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto cur:a[u])
		{
			long long nu=cur.to;
			long long w=cur.w;
			if(rdis[u]+w<rdis[nu])
			{
				rdis[nu]=rdis[u]+w;
				q.push({rdis[nu],nu});
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(long long i=1;i<=m;i++)
	{
		long long u,v,w;
		cin>>u>>v>>w;
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
	dijkstra_1();
	dijkstra_n();
	for(long long i=1;i<=n;i++)
	{
        if(dis[i]!=0x3f3f3f3f3f && rdis[i]!=0x3f3f3f3f3f)
        {
            long long mx=max(dis[i],rdis[i]);
    		if(mx<ans)
    		{
    			ans=mx;
    			s.clear();
    			s.push_back(i);
    		} 
    		else if(mx==ans)
    		{
    			s.push_back(i);
    		}            
        }
		long long mx=max(dis[i],rdis[i]);

	}
	cout<<ans<<"\n";
    sort(s.begin(), s.end());
	for(long long i=0;i<s.size();i++)
	{
		cout<<s[i]<<" ";
	}cout<<"\n";
	return 0;
}