QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#781647#7883. Takeout Deliveringpcc1WA 314ms70560kbC++141.8kb2024-11-25 16:46:022024-11-25 16:46:22

Judging History

你现在查看的是最新测评结果

  • [2024-11-25 16:46:22]
  • 评测
  • 测评结果:WA
  • 用时:314ms
  • 内存:70560kb
  • [2024-11-25 16:46:02]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m;
struct node{
	int u,v,w;
}a[N];
struct Node{
	int fr,to,nxt,w;
}e[N*2];
int f[N],tot,head[N];
void add(int a,int b,int w){
	e[++tot].fr=a;
	e[tot].nxt=head[a];
	head[a]=tot;
	e[tot].to=b;
	e[tot].w=w;
}
int find(int x){
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
int dis1[N],dis2[N];
void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		dis1[v]=max(dis1[u],e[i].w);
		dfs(v,u);
	}
}
bool cmp(node a,node b){
	return a.w<b.w;
} 
signed main(){
	int ans=2e18;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int u,v,w,i=1;i<=m;i++){
		cin>>a[i].u>>a[i].v>>a[i].w;
		if(a[i].u==1&&a[i].v==n){
			ans=min(ans,a[i].w);
		}
		if(a[i].u==n&&a[i].v==1){
			ans=min(ans,a[i].w);
		}
	}
	sort(a+1,a+m+1,cmp);
//	for(int i=1;i<=m;i++){
//		cout<<a[i].u<<" "<<a[i].v<<":\n";
//	}
	for(int i=1;i<=m;i++){
		int x=find(a[i].u);int y=find(a[i].v);
		if(x!=y){
			f[x]=y;
			add(a[i].u,a[i].v,a[i].w);
			add(a[i].v,a[i].u,a[i].w);
		}
	//	add(a[i].u,a[i].v);add(a[i].v,a[i].u);
	}
	dfs(1,0);
	swap(dis2,dis1);
//	for(int i=1;i<=n;i++){
//		cout<<dis2[i]<<" ";
//	}c
//	cout<<"\n";
	dfs(n,0);
	//ans=2e9;
//	if(n==300000){
//		for(int i=1;i<=n;i++){
//			cout<<dis1[i]<<" ";
//		}
//	}
	int cnt=2e9+10;
	for(int i=1;i<=m;i++){
		if(n==300000)cout<<e[i].w<<" "<<dis1[e[i].fr]<<" "<<dis2[e[i].to]<<"\n";
		if(dis1[e[i].fr]<=e[i].w&&dis2[e[i].to]<=e[i].w)cnt=min(cnt,max(dis1[e[i].fr],dis2[e[i].to])+e[i].w);
		if(dis2[e[i].fr]<=e[i].w&&dis1[e[i].to]<=e[i].w)cnt=min(cnt,max(dis1[e[i].to],dis2[e[i].fr])+e[i].w);
	}
	cout<<cnt<<"\n";
	return 0;
}



详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 25408kb

input:

4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: -100
Wrong Answer
time: 314ms
memory: 70560kb

input:

300000 299999
80516 80517 597830404
110190 110191 82173886
218008 218009 954561262
250110 250111 942489774
66540 66541 156425292
34947 34948 239499776
273789 273790 453201232
84428 84429 439418398
98599 98600 326095035
55636 55637 355015760
158611 158612 684292473
43331 43332 43265001
171621 171622 ...

output:

1925 999980151 999996532
1925 999980151 999996532
11047 999260250 999996532
11047 999260250 999996532
11374 999996532 999995165
11374 999996532 999995165
14882 999980151 999996532
14882 999980151 999996532
22481 999964329 999996532
22481 999964329 999996532
24168 999996532 999995165
24168 999996532 ...

result:

wrong answer 1st numbers differ - expected: '1999991697', found: '1925'