传送门
题目大意
有编号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[100100];priority_queue<pair<int,int> >q;map<int,int>is[100100];int d[100100],vis[100100];inline int wh(int id,int time){ ?????int res=0,i; ?????for(i=time;i<=1000000000;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=1;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=1;i<=n;i++){ ?????????int t,x; ?????????scanf("%d",&t); ???????????for(j=1;j<=t;j++){ ???????????????scanf("%d",&x); ???????????????is[i][x]=1; ???????????} ?????} ?????memset(d,0x3f,sizeof(d)); ?????d[1]=0; ?????q.push(make_pair(0,1)); ?????while(!q.empty()){ ?????????int x=q.top().second; ?????????q.pop(); ?????????if(x==n)break; ?????????if(vis[x])continue; ?????????vis[x]=1; ?????????d[x]+=wh(x,d[x]); ?????????for(i=0;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 0;}229B Planets
原文地址：https://www.cnblogs.com/yzxverygood/p/9444299.html