题目大意
有编号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
",d[n]);
return 0;
}