QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#663811#7883. Takeout Delivering111111qqqqqqWA 143ms56744kbC++232.2kb2024-10-21 17:34:562024-10-21 17:34:57

Judging History

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

  • [2024-10-21 17:34:57]
  • 评测
  • 测评结果:WA
  • 用时:143ms
  • 内存:56744kb
  • [2024-10-21 17:34:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
#define modd(a,b) a=a%b
#define pb push_back
#define db double
#define lowbit(x) x&(-x)
#define cerr(x) cout<<#x<<"="<<x<<endl
const ll mod=1e9+7;
ll ksm(ll a,ll b) {ll ans=1,bs=a;while(b) {if(b&1) ans=ans*bs%mod;bs=bs*bs%mod;b>>=1;}return ans;}
#define fi first
#define se second
#define N 300010
#define M 1000010
int n,m;
int fa[N],tot=0;
int dep[2][N];
ll dis[2][N];
vector<pair<int,ll>>to[N];
struct edge{int x,y;ll w;}e[M],g[M];
void add(int a,int b,ll c) {to[a].pb({b,c});}
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y,ll w) {
    int fx=find(x),fy=find(y);
    if(fx==fy) return;
    fa[fx]=fy;
    g[++tot]=(edge){x,y,w};
}
void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) {
        int a,b,c;cin>>a>>b>>c;
        e[i]=(edge){a,b,c};
    }
    sort(e+1,e+m+1,[&](edge a,edge b){return a.w<b.w;});
    for(int i=1;i<=m;i++) {
        auto [x,y,w]=e[i];
        merge(x,y,w);
        if(tot==n-1) break;       
    }
    for(int i=1;i<=tot;i++) {
        auto [x,y,w]=g[i];
        add(x,y,w),add(y,x,w);
    }
    auto dfs=[&](auto self,int u,int type,int fa)->void {
        dep[type][u]=dep[type][fa]+1;
        for(auto [v,w]:to[u]) {
            if(v==fa) continue;
            dis[type][v]=dis[type][u]+w;
            self(self,v,type,u);
        }
    };
    dfs(dfs,1,0,0);
    dfs(dfs,n,1,0);
    ll ans=1e18,tmp=0;
    for(int i=1;i<=m;i++) {
        auto [x,y,fir]=e[i];
        if(x==1 && y==n) cmin(ans,fir);
        if(x==n && y==1) cmin(ans,fir);
        ll sec;
        if(dep[0][x]>dep[0][y]) swap(x,y);
        sec=min(dis[0][x]+dis[1][y],dis[1][x]+dis[0][y]);
        cmin(ans,fir+sec);
    }
    // for(int i=1;i<=n;i++) cout<<dis[1][i]<<" ";cout<<endl;    
    cout<<ans<<endl;
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // int T;
    // cin>>T;
    // while(T--) 
    solve();
    return 0;
}
/*
最大值可以看作是枚举当前的最大值然后2个端点分别和1,n进行取max然后加和即可
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7788kb

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: 143ms
memory: 56744kb

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:

149949075068663

result:

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