http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11444
【题意】给一张无向图 求从点0到点n-1 花费的最少时间 每条路径有一段开放的时间 每天只有在这段时间汽车才能开上这条路 汽车从中午（ 即第720分钟 ）开始走 一开始车里的电可以走4小时 每到一个点可以充电 充两分钟可以走一分钟
【只过了 测试数据 代码先贴在这里】
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<math.h> #include<string> #include<queue> #define maxx 100000000 using namespace std; struct node { int t; int s; int e; int w; }; vector<node > g[502]; bool vis[502]; int d[502],n,rest[502]; queue<int > q; int spfa(int s,int ans) { memset(vis,false,sizeof(vis)); q.push(s); vis[s]=true; for(int i=0; i<=n; i++) d[i]=maxx; d[s]=720; rest[s]=240; while(!q.empty()) { int u; u=q.front(); q.pop(); vis[u]=false; for(int i=0; i<g[u].size(); i++) { int v,time; v=g[u][i].t; time=g[u][i].w; int temp=0,temp1=0;//加油等待的时间 在u点等待的时间 if(d[u]<=g[u][i].e) { if(d[u]<=g[u][i].s) temp1=g[u][i].s-d[u]; int you; you=rest[u]+temp1/2; if(you>240) you=240; //油最多只能加到240 if(you>=time) // 油够 { rest[v]=you-time; } else //油不够 { if(temp1%2==1&&you<240) { temp1++;//多充一分钟 把充完走一分钟的电 you++; } temp+=(time-you)*2; //加油的时间 if(temp<=g[u][i].e-g[u][i].s) { rest[v]=0; } else continue; } if(d[v]>d[u]+temp+time+temp1) { d[v]=d[u]+temp+time+temp1; if(vis[v]==false) { q.push(v); vis[v]=true; } } } } } return d[ans]; } int main() { int m,s,t,e,w,a,b; while(scanf("%d%d",&n,&m)>0) { if(n==0&&m==0) break; for(int i=0; i<=n; i++) g[i].clear(); for(int i=0; i<m; i++) { scanf("%d%d",&a,&b); while(1) { scanf("%d%d%d",&s,&e,&w); if(w>240&&e==1439) break; else if(w>240) continue; for(int k=0; k<100; k++) { node temp; temp.t=b; temp.s=s+1440*k; temp.e=e+1440*k; temp.w=w; g[a].push_back(temp); temp.t=a; g[b].push_back(temp); } if(e==1439) break; } } printf("%d ",spfa(0,n-1)-720); } return 0; }