Gremlins have infested the farm. These nasty, ugly fairy-like
creatures thwart the cows as each one walks from the barn (conveniently located at pasture_1) to the other fields, with cow_i traveling to from pasture_1 to pasture_i. Each gremlin is personalized and knows the quickest path that cow_i normally takes to pasture_i. Gremlin_i waits for cow_i in the middle of the final cowpath of the quickest route to pasture_i, hoping to harass cow_i.
Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly different route from pasture_1 (the barn) to pasture_i.
Compute the best time to traverse each of these new not-quite-quickest routes that enable each cow_i that avoid gremlin_i who is located on the final cowpath of the quickest route from pasture_1 to
pasture_i.
As usual, the M (2 <= M <= 200,000) cowpaths conveniently numbered 1..M are bidirectional and enable travel to all N (3 <= N <= 100,000) pastures conveniently numbered 1..N. Cowpath i connects pastures a_i (1 <= a_i <= N) and b_i (1 <= b_i <= N) and requires t_i (1 <= t_i <= 1,000) time to traverse. No two cowpaths connect the same two pastures, and no path connects a pasture to itself (a_i != b_i). Best of all, the shortest path regularly taken by cow_i from pasture_1 to pasture_i is unique in all the test data supplied to your program.
By way of example, consider these pastures, cowpaths, and [times]:
1--[2]--2-------+
| | |
[2] [1] [3]
| | |
+-------3--[4]--4
TRAVEL BEST ROUTE BEST TIME LAST PATH
p_1 to p_2 1->2 2 1->2
p_1 to p_3 1->3 2 1->3
p_1 to p_4 1->2->4 5 2->4
When gremlins are present:
TRAVEL BEST ROUTE BEST TIME AVOID
p_1 to p_2 1->3->2 3 1->2
p_1 to p_3 1->2->3 3 1->3
p_1 to p_4 1->3->4 6 2->4
For 20% of the test data, N <= 200.
For 50% of the test data, N <= 3000.
TIME LIMIT: 3 Seconds
MEMORY LIMIT: 64 MB
Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的 地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它 们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找 一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最 短路经的长度.
和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到 达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i (1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过. 没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛 棚_i的最短路经是唯一的.
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Three space-separated integers: a_i, b_i, and t_i
* Lines 1..N-1: Line i contains the smallest time required to travel from pasture_1 to pasture_i+1 while avoiding the final cowpath of the shortest path from pasture_1 to pasture_i+1. If no such path exists from pasture_1 to pasture_i+1, output -1 alone on the line.
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
3
3
6
最后放一下代码，千万别用SPFA，会T掉很多。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 #include <cstring> 6 #include <queue> 7 using namespace std; 8 const int maxn = 100010; 9 const int maxm = 400010; 10 11 inline int read() 12 { 13 int res = 0; 14 bool flag = 0; 15 char c = getchar(); 16 while (c < ‘0‘ or c > ‘9‘) 17 { 18 if (c == ‘-‘) flag = 1; 19 c = getchar(); 20 } 21 while (c >= ‘0‘ and c <= ‘9‘) 22 { 23 res = res * 10 + c - ‘0‘; 24 c = getchar(); 25 } 26 return flag ? -res : res; 27 } 28 29 int n, m; 30 int a [maxm], b[maxm], c[maxm]; 31 int what[maxm]; 32 int ins[maxm]; 33 bool iiis[maxm]; 34 int father[maxn]; 35 int fa[maxn]; 36 int ans[maxn]; 37 38 int find(int x) 39 { 40 return x==fa[x]?x:fa[x]=find(fa[x]); 41 } 42 43 struct edge 44 { 45 int next; 46 int to; 47 int val; 48 }way[maxm]; 49 50 int head[maxn], tot; 51 inline void add (int x , int y , int z , int GG) 52 { 53 way[++tot].next = head[x]; 54 way[tot].to = y; 55 way[tot].val = z; 56 what[tot] = GG; 57 head[x] = tot; 58 } 59 inline void add (int x , int y) 60 { 61 way[++tot].next = head[x]; 62 way[tot].to=y; 63 head[x]=tot; 64 } 65 struct date 66 { 67 int x; 68 int y; 69 int w; 70 }usaco[maxm]; 71 72 bool cmp(date a, date b) 73 { 74 return a.w < b.w; 75 } 76 77 78 int dfs(int x) 79 { 80 for(int i=head[x];i;i=way[i].next) 81 { 82 int to=way[i].to; 83 if(to==father[x]) 84 { 85 continue; 86 } 87 father[to]=x; 88 dfs(to); 89 } 90 } 91 92 struct dij{int x, w;}; 93 94 bool operator <(const dij &a,const dij &b) 95 { 96 return a.w > b.w; 97 } 98 99 int dis[maxn]; 100 bool vis[maxn]; 101 102 int dijkstra(int qa) 103 { 104 memset(dis,0x3f,sizeof(dis)); 105 priority_queue < dij > q; 106 dis[qa]=0; 107 q.push((dij){qa,0}); 108 while(!q.empty()) 109 { 110 dij t=q.top(); 111 q.pop(); 112 int x=t.x; 113 if(vis[x]) 114 { 115 continue; 116 } 117 vis[x]=1; 118 for(int i=head[x];i;i=way[i].next) 119 { 120 int to=way[i].to; 121 if(!vis[to]&&dis[to]>dis[x]+way[i].val) 122 { 123 ins[to]=what[i]; 124 dis[to]=dis[x]+way[i].val; 125 q.push((dij){to,dis[to]}); 126 } 127 } 128 } 129 } 130 int main() 131 { 132 //freopen("testdata.in","r",stdin); 133 n=read(); 134 m=read(); 135 for(int i=1;i<=m;i++) 136 { 137 a[i]=read(); 138 b[i]=read(); 139 c[i]=read(); 140 add(a[i],b[i],c[i],i); 141 add(b[i],a[i],c[i],i); 142 } 143 dijkstra(1); 144 tot=0; 145 memset(head,0,sizeof(head)); 146 for(int i=2;i<=n;i++) 147 { 148 int x=ins[i]; 149 add(a[x],b[x]); 150 add(b[x],a[x]); 151 iiis[x]=1; 152 } 153 dfs(1); 154 int sum=0; 155 for(int i=1;i<=m;i++) 156 { 157 if(iiis[i]) 158 { 159 continue; 160 } 161 usaco[++sum]=(date){a[i],b[i],dis[a[i]]+dis[b[i]]+c[i]}; 162 } 163 sort(usaco+1,usaco+1+sum,cmp); 164 for(int i=1;i<=n;i++) 165 { 166 fa[i]=i; 167 ans[i]=-1; 168 } 169 for(int i=1;i<=sum;i++) 170 { 171 int x=usaco[i].x; 172 int y=usaco[i].y; 173 x=find(x); 174 y=find(y); 175 while(x!=y) 176 { 177 if(dis[x]<dis[y]) 178 { 179 swap(x,y); 180 } 181 ans[x]=usaco[i].w-dis[x]; 182 fa[x]=father[x]; 183 x=find(x); 184 } 185 } 186 for(int i=2;i<=n;i++) 187 { 188 printf("%d\n",ans[i]); 189 // cout<<ans[i]<<endl; 190 } 191 return 0; 192 }
「BZOJ1576」[Usaco2009 Jan] 安全路经Travel------------------------P2934 [USACO09JAN]安全出行Safe Travel
原文：https://www.cnblogs.com/2529102757ab/p/11441774.html