QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#781523 | #7883. Takeout Delivering | pcc1 | WA | 274ms | 70500kb | C++14 | 1.5kb | 2024-11-25 16:20:55 | 2024-11-25 16:20:56 |
Judging History
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].nxt=head[a];
head[a]=tot;
e[tot].to=b;
e[tot].w=w;
e[tot].fr=a;
}
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>>u>>v>>w;
a[i].u=u;
if(u==1&&v==n){
ans=min(ans,w);
}
if(u==n&&v==1){
ans=min(ans,w);
}
a[i].v=v;
a[i].w=w;
}
sort(a+1,a+m+1,cmp);
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);
dfs(n,0);
for(int i=1;i<=m;i++){
if(dis1[e[i].fr]<=e[i].w&&dis2[e[i].to]<=e[i].w)ans=min(ans,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)ans=min(ans,max(dis1[e[i].to],dis2[e[i].fr])+e[i].w);
}
cout<<ans<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 25400kb
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: 274ms
memory: 70500kb
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:
2000000000000000000
result:
wrong answer 1st numbers differ - expected: '1999991697', found: '2000000000000000000'