【Codeforces 229B】Planets

【题解】

设dis[i]表示到达i号传送器的最早时刻.
显然,虽然有那么多的出发时刻的限制,但我们还是越早到越好的.
因为你到得越早,出发的时间肯定不会比到达的时刻晚的差.
所以,就是一个最短路的问题啦.
因为数据范围比较大.
所以得用dijkstra+优先队列的优化.
在出去的时候,只要枚举一遍到达这个点的所有时刻,就能知道它啥时候出发了.
因为∑ki

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

using namespace std;

const int N = 1e5;

int n,m;

vector<pair<int,int> > g[N+10];

vector<int> a[N+10];

int dis[N+10];

priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > pq;

int main()

{

    scanf("%d%d",&n,&m);

    rep1(i,1,m){

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        g[x].push_back(make_pair(y,z));

        g[y].push_back(make_pair(x,z));

    }

    for (int i = 1;i <= n;i++){

        int cnt;

        scanf("%d",&cnt);

        rep1(j,0,cnt-1){

            int x;

            scanf("%d",&x);

            a[i].push_back(x);

        }

    }

    rep1(i,1,n) dis[i] = -1;

    dis[1] = 0;

    pq.push(make_pair(0,1));

    while (!pq.empty()){

        pair<LL,int> temp = pq.top();pq.pop();

        int x = temp.second;LL disx = temp.first;

        if (dis[x]<disx) continue;

        rep1(i,0,(int)a[x].size()-1)

            if (a[x][i]==disx)

                disx++;

        for (pair<int,int> temp1:g[x]){

            int y = temp1.first,cost = temp1.second;

            if (dis[y]==-1 || dis[y]>cost+disx){

                dis[y] = cost+disx;

                pq.push(make_pair(dis[y],y));

            }

        }

    }

    cout<<dis[n]<<endl;

    return 0;

}

巴特西

【Codeforces 229B】Planets

最新文章

热门文章