列表

详情

NC24824. [USACO 2009 Jan G]Safe Travel

描述

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 (). 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.

输入描述

* 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  while avoiding the final cowpath of the shortest path from pasture_1 to . If no such path exists from pasture_1 to , output -1 alone on the line.

示例1

输入: 

4 5 
1 2 2 
1 3 2 
3 4 4 
3 2 1 
2 4 3

输出: 

3
3
6

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 179ms, 内存消耗: 22304K, 提交时间: 2019-09-21 08:53:47 

#include<bits/stdc++.h>

using namespace std;

typedef long long int_t;

const int_t maxn = 100010;
const int_t inf = 2147483647;

int_t dis[maxn],frm[maxn],fa[maxn],ans[maxn];

struct node{
	int_t a,b,c;
	node(int_t a,int_t b,int_t c):a(a),b(b),c(c){}
};

struct E{
	int_t u,v,w;
	E(int_t u=0,int_t v=0,int_t w=0):u(u),v(v),w(w){}
}Es[maxn<<1];

bool operator <(node a,node c){return a.b > c.b;}

priority_queue<node> pque;
vector<pair<int_t,int_t> > G[maxn];

void dijkstra(int_t n){
	for(int_t i=1;i<=n;i++) dis[i] = inf;
	pque.push(node(1,0,0));
	while(!pque.empty()){
		node tp = pque.top();pque.pop();
		if(dis[tp.a] != inf) continue;
		int_t rt = tp.a; dis[rt] = tp.b;frm[rt] = tp.c;
		for(pair<int_t,int_t> e : G[rt]) if(dis[e.first] == inf) pque.push(node(e.first,e.second + dis[rt],rt));
	}
}	

int_t read(){
	int_t x = 0,w = 1;char ch = 0;
	while(!isdigit(ch)) {ch = getchar();if(ch == '-') w = -1;}
	while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return x * w;
}

int_t find(int_t rt){return rt == fa[rt] ? rt : fa[rt] = find(fa[rt]);}

int main(){
	int_t n = read(),m = read(),tmp=0,ttp=0;
	while(m--){
		int_t u = read(),v = read(), w = read();
		G[u].push_back(make_pair(v,w));
		G[v].push_back(make_pair(u,w));
	}
	dijkstra(n);
	for(int_t i=1;i<=n;i++){
		fa[i] = i;ans[i] = inf;
		for(auto e : G[i])
			if(frm[i] != e.first && frm[e.first] != i && e.first > i)
				Es[++tmp] = E(i,e.first,e.second+dis[i]+dis[e.first]);
	}
	sort(Es+1,Es+tmp+1,[](E a,E b){return a.w < b.w;});
	for(int_t i=1;i<=tmp && ttp < n-1;i++){
		int_t u = Es[i].u,v = Es[i].v,w = Es[i].w;
		while(find(u) != find(v)){
			++ttp;
			if(dis[find(u)] < dis[find(v)]) swap(u,v);
			ans[find(u)] = min(ans[find(u)],w - dis[find(u)]);
			fa[find(u)] = frm[find(u)];
			u = fa[find(u)];
		}
	}
	for(int_t i=2;i<=n;i++)
		printf("%lld\n",ans[i] == inf ? -1 : ans[i]);
}

C++11(clang++ 3.9) 解法, 执行用时: 106ms, 内存消耗: 10460K, 提交时间: 2019-09-21 09:13:15 

#include<bits/stdc++.h>
#define in read()
#define re register
#define ll long long 
using namespace std;
inline int read(){
	char ch;int f=1,res=0;
	while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^48);
		ch=getchar();
	}
	return f==1?res:-res;
}
const int N=1e5+10,M=4e5+10;
bool vis[N];
int n,m,tfa[N],d[N],fa[N],ans[N];
int nxt[M],head[N],ecnt=0,cnt=0;
struct node{int u,v,w;}e[M],tree[M];
inline bool cmp(const node &a,const node &b){return a.w<b.w;}
inline void add(int x,int y,int z){
	nxt[++ecnt]=head[x];head[x]=ecnt;
	e[ecnt].u=x;e[ecnt].v=y;e[ecnt].w=z;
}
inline int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void dij(){
	priority_queue<pair<int,int> > q;
	memset(d,127/3,sizeof(d));
	q.push(make_pair(0,1));d[1]=0;
	while(!q.empty()){
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(re int i=head[u];i;i=nxt[i]){
			int v=e[i].v;
			if(d[v]>d[u]+e[i].w){
				d[v]=d[u]+e[i].w;
				tfa[v]=u;
				q.push(make_pair(-d[v],v));
			}
		}
	}
}
int main(){
	n=in;m=in;
	for(re int i=1;i<=m;++i){
		int x,y,z;
		x=in;y=in;z=in;
		add(x,y,z);add(y,x,z);
	}
	dij();
	for(re int i=1;i<=2*m;i+=2){//寻找非树边 
		int u=e[i].u,v=e[i].v;
		if(tfa[u]==v||tfa[v]==u) continue;
		tree[++cnt].w=d[u]+e[i].w+d[v];
		tree[cnt].u=u;
		tree[cnt].v=v;
	}
	sort(tree+1,tree+cnt+1,cmp);
	memset(ans,-1,sizeof(ans));
	for(re int i=1;i<=n;++i) fa[i]=i;
	for(re int i=1;i<=cnt;++i){
		int u=getfa(tree[i].u),v=getfa(tree[i].v);
		while(u!=v){//把这条非树边能够更新的都更新 
			if(d[u]<d[v]) swap(u,v);
			ans[u]=tree[i].w-d[u];
			fa[u]=tfa[u];
			u=getfa(u);
		}
	}
	for(re int i=2;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}

上一题

© 2025 nowcoder.com