P7192 [COCI 2007/2008 #6] GEORGE题目背景T 先生来 Luka 所在的小镇玩因为 T 先生是一个大人物警察会对他将走过的路实行交通管制。Luka 在镇上是一名送货的卡车司机。但是由于一些路正在进行交通管制他无法及时交货还因此差点丢掉了他的工作。题目描述Luka 知道 T 先生游玩的路线并且他想要知道最短的交货时间。该城市由若干十字路口和连接它们的道路连接并且 Luka 知道他需要在某条路段上开多长时间T 先生需要同样的时间以开过该路段。例如如果 T 先生在第10 1010分钟进入一条路并且需要5 55分钟离开这条路那么该街道将在第10 ∼ 14 10 \sim 1410∼14分钟时被封锁。Luka可以在第9 99分钟或更早的时候也可以在第15 1515分钟及以后进入该道路。编写一个程序计算 Luka 在 T 先生到达城市后k kk分钟开始开车的最短时间。输入格式第一行两个正整数n , m n, mn,m分别表示十字路口数和街道数。 十字路口编号为1 11到n nn。第二行四个正整数a , b , k , g a, b, k, ga,b,k,g分别表示a aaLuka 起点的路口。b bbLuka 必须到达的十字路口。k kkT 先生和 Luka 之间的出发时间差。g ggT 先生路上的十字路口数。第三行g gg个整数表示 T 先生路上依次经过的十字路口。保证存在对应的街道每条街道只能走一次。接下来m mm行每行三个整数a , b , l a, b, la,b,l表示在坐标( a , b ) (a, b)(a,b)处有一条街道开过去的时间为l ll。输出格式一行输出 Luka 送货需要的最短时间单位分。输入输出样例 #1输入 #16 5 1 6 20 4 5 3 2 4 1 2 2 2 3 8 2 4 3 3 6 10 3 5 15输出 #121输入输出样例 #2输入 #28 9 1 5 5 5 1 2 3 4 5 1 2 8 2 7 4 2 3 10 6 7 40 3 6 5 6 8 3 4 8 4 4 5 5 3 4 23输出 #240说明/提示数据规模及约定对于100 % 100\%100%的数据2 ≤ n ≤ 10 3 2 \le n \le 10^32≤n≤1032 ≤ m ≤ 10 4 2 \le m \le 10^42≤m≤1041 ≤ a , b ≤ n 1 \le a, b \le n1≤a,b≤n0 ≤ k ≤ 10 3 0 \le k \le 10^30≤k≤103$ 0 \le g \le 10^3$。说明本题满分60 6060分。本题默认开启 O2 优化开关。题目译自 COCI2007-2008 CONTEST #6 T4 GEORGE译者 tearing。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;inta[1005],pd[1005][1005],l[10005],r[100005];structf{intx,k;};vectorfs[1005];intpd1[1005][1005],cnt;intn,m,dis[1005],vis[1005];priority_queuepairint,intq;voiddij(intS,intt){for(inti1;in;i)dis[i]1e18,vis[i]0;dis[S]t;q.push(make_pair(-dis[S],S));while(q.size()){intpq.top().second;q.pop();if(vis[p])continue;vis[p]1;for(inti0;is[p].size();i){intys[p][i].x,ks[p][i].k,sum0,numpd[p][y];if(dis[p]l[num]dis[p]r[num]){sumr[num]-dis[p]1;//cout0;}if(dis[y]dis[p]ksum){dis[y]dis[p]ksum;q.push(make_pair(-dis[y],y));}}}}signedmain(){cinnm;intS,t,k,g;cinStkg;for(inti1;ig;i){cina[i];}for(inti1;im;i){intx,y,k;cinxyk;pd[x][y]cnt;pd[y][x]cnt;pd1[x][y]pd1[y][x]k;f op;op.xy,op.kk;s[x].push_back(op);op.xx;s[y].push_back(op);}intt10;for(inti1;ig;i){l[pd[a[i]][a[i1]]]t1;t1pd1[a[i]][a[i1]];r[pd[a[i]][a[i1]]]t1-1;}dij(S,k);coutdis[t]-k;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容