229B Planets

题目大意

有编号1~n的星球，在不用的星球间共有m个传送门，任意两个星球间传送门不超过1个，每个传送门需要花费一定的时间，但是在某时刻会在某星球有旅客到达，这时要一定等到没有旅客到达的时候才能出发，问从1走到n最少花费时间是多少。

分析

首先我们先考虑一个贪心策略，如果到达点i的时间有a和b（a<b），则从i出发前往n的途中使用时间为a的这一方案一定更优，即不存在一种情况使得某个点先到达的最终结果比后到达的坏，原因易证。然后计算最短路就可以了。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const int inf = 0x3f3f3f3f;

vector<pair<int,int> >v[];

priority_queue<pair<int,int> >q;

map<int,int>is[];

int d[],vis[];

inline int wh(int id,int time){

      int res=,i;

      for(i=time;i<=;i++)

        if(is[id][i])res++;

          else break;

      return res;

}

int main(){

      int n,m,i,j,k;

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

      for(i=;i<=m;i++){

          int x,y,z;

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

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

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

      }

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

          int t,x;

          scanf("%d",&t);

            for(j=;j<=t;j++){

                scanf("%d",&x);

                is[i][x]=;

            }

      }

      memset(d,0x3f,sizeof(d));

      d[]=;

      q.push(make_pair(,));

      while(!q.empty()){

          int x=q.top().second;

          q.pop();

          if(x==n)break;

          if(vis[x])continue;

          vis[x]=;

          d[x]+=wh(x,d[x]);

          for(i=;i<v[x].size();i++){

            int y=v[x][i].first,z=v[x][i].second;

            if(d[y]>d[x]+z){

                d[y]=d[x]+z;

                q.push(make_pair(-d[y],y));

            }

          }

      }

      if(d[n]>=inf)puts("-1");

        else printf("%d\n",d[n]);

      return ;

}

巴特西

229B Planets

最新文章

热门文章