Ramen Network Protocol

The input contains multiple lines.

The first line is four integers: n, m, s, t(1 <= n <= 1e4, 1 <= m <= 5e4, 1 <= s,t <= n, s+t <= n), represents the number of nodes, RFs, senders and receivers.

The second line contains exactly s integers S1...Ss, each represents a distinct sender, for all 1 <= i <= s, 1 <= Si <= n.

The third line contains exactly t integers T1...Tt, each represents a distinct receiver, for all 1 <= i <= t, 1 <= Ti <= n.

Each of the next m lines contains three integers: u, v, w(1 <= u, v <= n, u ≠ v, 1 <= w <= 1e9), means that there is an RF between node u to node v and the time needed for a packet to go through it. All RFs are distinct.

It's guaranteed that no point is a sender and a receiver simultaneously.

C++14(g++5.4) 解法, 执行用时: 21ms, 内存消耗: 4328K, 提交时间: 2019-04-14 12:24:23

#include<bits/stdc++.h>
#define N 100005
#define int long long
#define inf 2e16
using namespace std;

inline void read(int &X)
{
    X=0;int w=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    X=w?-X:X;
}
int n,m,s,t;
int head[N],cnt,dis[N],v[N];
struct nd{int next,to,v;}e[N*5];

void add(int x,int y,int v)
{
    e[++cnt]=(nd){head[x],y,v};head[x]=cnt;
}
void dj(int s)
{
    memset(v,0,sizeof v);
    priority_queue< pair<int,int> > q;
    for(int i=1;i<=n+2;i++) dis[i]=inf;
    dis[s]=0;q.push(make_pair(0,s));
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(v[x]) continue;v[x]=1;
        for(int y,i=head[x];i;i=e[i].next)
            if(dis[y=e[i].to]>dis[x]+e[i].v)
                dis[y]=dis[x]+e[i].v,q.push(make_pair(-dis[y],y));
    }

}
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(int x,i=1;i<=s;i++)
        read(x),add(n+1,x,0);
    for(int x,i=1;i<=t;i++)
        read(x),add(x,n+2,0);
    for(int x,y,v,i=1;i<=m;i++)
        read(x),read(y),read(v),add(x,y,v),add(y,x,v);
    dj(n+1);
    if(dis[n+2]==inf) puts("-1");
    else cout<<dis[n+2];
}

C++ 解法, 执行用时: 68ms, 内存消耗: 7272K, 提交时间: 2022-07-13 00:35:31

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f
typedef long long ll;
struct Edge
{
	ll to;
	ll nxt;
	ll w;
}edge[1000010];
ll tot=0,head[100010],vis[100010]; 
void add(ll u,ll v,ll w)
{
	edge[++tot].to=v; edge[tot].nxt=head[u]; edge[tot].w=w; head[u]=tot;
	edge[++tot].to=u; edge[tot].nxt=head[v]; edge[tot].w=w; head[v]=tot;
}
ll n,m,s,t,inq[210100],dis[210100];
void spfa(int u)
{
	memset(dis,INF,sizeof(dis));
	memset(inq, 0 ,sizeof(inq));
	queue<int>q;
	q.push(u);inq[u]=1;dis[u]=0;
	while(!q.empty())
	{
		int t=q.front();
		q.pop(); inq[t]=0;
		for(int i=head[t];~i;i=edge[i].nxt)
		{
			Edge e=edge[i];
			if(dis[e.to]>dis[t]+e.w)
			{
				dis[e.to]=dis[t]+e.w;
				if(!inq[e.to])
				{
					inq[e.to]=1;
					q.push(e.to);
				}
			}
		} 
	}
}
int main()
{
	memset(head,-1,sizeof(head));
	cin>>n>>m>>s>>t;
	for(int i=1;i<=s;i++) 
	{
		ll s; cin>>s;
		add(0,s,0);
	}
	for(int i=0;i<t;i++) 
	{
		ll t; cin>>t;
		add(t,n+1,0);
	}
	for(int i=1;i<=m;i++)
	{
		ll u,v,w; cin>>u>>v>>w;
		add(u,v,w);
	}
	spfa(0);
	if(dis[n+1]-INF<1) cout<<dis[n+1]<<endl;
	else cout<<"-1"<<endl;
	return 0;
}

详情