C++(g++ 7.5.0) 解法, 执行用时: 549ms, 内存消耗: 69016K, 提交时间: 2023-05-25 12:16:05

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define ios::ios_sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef pair<int,int> pii;
const int N=1e6+10;
int n,m;
vector<pair<int ,int >>mp[N];
int a[2*N];
int b[2*N];
int st[2*N];
int u[2*N];
void dj(int (&dis)[2*N],int start){
	memset(dis,0x3f,sizeof(dis));
	memset(st,0,sizeof(st));
	priority_queue<pii,vector<pii>,greater<pii>> q;
	q.push({0,start});
	dis[start]=0;
	while(!q.empty()){
		auto T=q.top();
		q.pop();
		int t=T.second;
		int ds=T.first;
		st[t]=1;
	//	cout<<t<<" "<<ds<<endl;
		for(auto &e:mp[t]){
			int ne=e.first;
			int w=e.second;
			if(!st[ne]&&dis[ne]>dis[t]+w){
				dis[ne]=dis[t]+w;
				q.push({dis[ne],ne});
			}
		}
	} 
}
void sove(){
	dj(a,1);
	dj(b,n);
	ll ans=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		ans=min(ans,(ll)max(a[i],b[i]));
	}
	if(ans==0x3f3f3f3f)cout<<"-1";
	else{
		cout<<ans<<endl;
		for(int i=1;i<=n;i++){
		if(ans==max(a[i],b[i])){
			cout<<i<<" ";
		}
	}
	}
	
}
signed main(){
    cin>>n>>m;
    for(int j=1;j<=m;j++){
    	int s,t;
    	cin>>t>>s;
        while(s--){
        	int tmp;
        	cin>>tmp;
        	mp[tmp].push_back({tmp,0});
        		mp[n+j].push_back({tmp,0});
        		mp[tmp].push_back({n+j,t});
		}
	}
	
	sove();
	return 0;
}

C++ 解法, 执行用时: 431ms, 内存消耗: 20748K, 提交时间: 2022-07-05 11:00:11

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
const int N = 4e5+10,M = 2e7 + 10;
long long int dist[N],backup[N];
int h[N],e[M],ne[M],idx,w[M];
bool st[N];
typedef pair<int,int>PII;

void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dijkstra(int op)
{
	memset(dist,0x3f3f3f3f,sizeof(dist));
	dist[op]=0;
	priority_queue<PII,vector<PII>,greater<PII> >q;
	q.push({0,op});
	while(!q.empty())
	{
		auto r=q.top();
		q.pop();
		int k=r.second,l=r.first;
		if(st[k])continue;
		st[k]=true;
		for(int i=h[k];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dist[j]>dist[k]+w[i])
			{
				dist[j]=dist[k]+w[i];
				q.push({dist[j],j});
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=m;i++)
	{
		int s,t;
		cin>>t>>s;
		while(s--)
		{
			int r;
			cin>>r;
			add(i+100000,r,t);
			add(r,i+100000,t);
		}
	}
	
	dijkstra(1);
	for(int i=1;i<=n;i++)backup[i]=dist[i];
	memset(st,false,sizeof(st));
	dijkstra(n);
	long long ans=1e18;
	for(int i=1;i<=n;i++)
	{
			ans=min(ans,max(backup[i],dist[i]));
	}
	if(ans==1e18)cout<<-1<<endl;
	else{
		cout<<ans/2<<endl;
		for(int i=1;i<=n;i++)
			if(max(backup[i],dist[i])==ans)cout<<i<<' ';
	}
	return 0;
}