[SDOI2010]大陆争霸

第一行两个正整数 N, M。

接下来 M行，每行三个正整数 u_i, v_i, w_i，表示有一条从城市u_i到城市 v_i的单向道路，自爆机器人通过这条道路需要 w_i的时间。

之后 N 行，每行描述一个城市。首先是一个正整数 l_i，维持这个城市结界所使用的结界发生器数目。

之后l_i个1~N 之间的城市编号，表示每个结界发生器的位置。如果 L_i = 0，则说明该城市没有结界保护，保证L₁ = 0 。

C++(g++ 7.5.0) 解法, 执行用时: 12ms, 内存消耗: 2256K, 提交时间: 2023-02-14 21:52:35

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#define ll long long
#define reg register
#define fo(a,b,c) for(reg int a=b;a<=c;a++)
#define re(a,b,c) for(reg int a=b;a>=c;a--)
#define pii pair<int,int>
#define fi first
#define se second
#define mod 1000000007
using namespace std;
inline ll gi(){
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
struct cop
{
	bool operator()(pii a,pii b)
	{
		return a.fi>b.fi;
	}
};
priority_queue<pii,vector<pii>,cop> q;
ll _=1;
struct io
{
	ll u,v,w;
}node[70005];
struct oi
{
	ll u,v;
}node1[5000005];
ll head[3005],dis[3005],head1[3005],cnt1,cnt,km[3005],ar[3005],in[3005],vis[3005];
void dij()
{
	while(!q.empty())
	{
		pii u=q.top();
		q.pop();
		if(vis[u.se]) continue;
		vis[u.se]=1;
		for(ll i=head1[u.se];i;i=node1[i].u)
		{
			ll v=node1[i].v;
			in[v]--;
			km[v]=max(km[v],ar[u.se]);
			if(in[v]==0)
			{
				if(ar[v]<99999999999999)
				{
					ar[v]=max(ar[v],km[v]);
					q.push({ar[v],v});
				}
			}
		}
		for(ll i=head[u.se];i;i=node[i].u)
		{
			ll v=node[i].v;
			if(in[v])
			{
				ar[v]=min(ar[v],ar[u.se]+node[i].w);
				continue;
			}
			if(ar[u.se]+node[i].w<ar[v])
			{
				ar[v]=ar[u.se]+node[i].w;
				q.push({ar[v],v});
			}
		}
	}
}
void add(ll u,ll v,ll w)
{
	cnt++;
	node[cnt].u=head[u];
	head[u]=cnt;
	node[cnt].v=v;
	node[cnt].w=w;
}
void add1(ll u,ll v)
{
	cnt1++;
	node1[cnt1].u=head1[u];
	head1[u]=cnt1;
	node1[cnt1].v=v;
}
void sol()
{
	memset(ar,0x3f,sizeof(ar));
	ll n=gi(),m=gi();
	ar[1]=0;
	fo(i,1,m)
	{
		ll x=gi(),y=gi(),z=gi();
		add(x,y,z);
	}
	fo(i,1,n)
	{
		ll k=gi();
		in[i]=k;
		fo(j,1,k)
		{
			ll x=gi();
			add1(x,i);
		}
	}
	q.push({0,1});
	dij();
	cout<<ar[n]<<'\n';
}
int main()
{
//	_=gi();
	while(_--)
	{
		sol();
//		cout<<'\n';
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 111ms, 内存消耗: 71636K, 提交时间: 2023-06-17 18:21:23

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
typedef long long ll;
using namespace std;
const int N=3010;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,cnt[N];
ll dist[N][N],d[N];
vector<int> jj[N];
bool vis[N];
void dijkstra() {
    memset(d,0x3f,sizeof d);
    priority_queue<pair<ll,int>> pq;
    pq.push({0,1});
    d[1]=0;
    while(!pq.empty()) {
        int x=pq.top().second;ll y=pq.top().first;pq.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int i=0;i<(int)jj[x].size();i++) {
            int t=jj[x][i];
            cnt[t]--;
            if(!cnt[t] && d[t]<INF) pq.push({-max(d[t],-y),t});
            d[t]=max(d[t],-y);
        }
        for(int i=1;i<=n;i++) {
            if(i==x || dist[x][i]>=INF) continue;
            if(d[i]>d[x]+dist[x][i]) {
                d[i]=d[x]+dist[x][i];
                if(!cnt[i]) pq.push({-d[i],i});
            }
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=n;i++) dist[i][i]=0;
    while(m--) {
        int u,v;ll w;
        scanf("%d%d%lld",&u,&v,&w);
        dist[u][v]=min(dist[u][v],w);
    }
    for(int i=1;i<=n;i++) {
        cin>>cnt[i];
        for(int j=1;j<=cnt[i];j++) {
            int obs;
            cin>>obs;
            jj[obs].push_back(i);
        }
    }
    dijkstra();
    cout<<d[n];
    return 0;
}

详情