QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#316282#8136. Rebellious EdgeLiberty12619TL 0ms3704kbC++201.8kb2024-01-27 19:16:562024-01-27 19:16:57

Judging History

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

  • [2024-01-27 19:16:57]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3704kb
  • [2024-01-27 19:16:56]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int> PII;
typedef unsigned long long ULL;
const int N = 5e5+10;
const int INF = 1e15;
vector<PII>g[N],h[N];
struct Edge
{
    int u,v,w;
};
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<Edge>edges(m+1);
    for(int i=1;i<=n;i++)
    {
        g[i].clear();
        h[i].clear();
    }
    array<int,3> tmp;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        if(u>v) tmp={u,v,w};
        g[v].push_back({w,u});
        edges[i]={u,v,w};
    }
    for(int i=1;i<=n;i++)   sort(g[i].begin(),g[i].end());
    int ans=0;
    for(int i=2;i<=n;i++)
    {
        int u = g[i][0].y,w=g[i][0].x;
        h[u].push_back({i,w});
        ans+=w;
    }
    vector<bool>st(n+1,0);
    queue<int>q;
    q.push(1);
    while(q.size())
    {
        int t = q.front();
        st[t]=true;
        q.pop();
        for(auto [x,y] : h[t])
        {
            if(st[x])   continue;
            q.push(x);
        }
    }
    bool ok = true;
    for(int i=1;i<=n;i++)
        if(!st[i])  ok=false;
    if(ok)
    {
        cout<<ans<<"\n";
        return;
    }
    ans=0;
    for(int i=1;i<=n;i++)   st[i]=false;
    int u = tmp[0],v=tmp[1];
    st[1]=true;
    while(u!=1)
    {
        st[u]=true;
        for(auto [x,y]: g[u])
        {
            if(y==v)    continue;
            ans+=x;
            u=y;
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(st[i])   continue;
        ans+=g[i][0].x;
    }
    cout<<ans<<"\n";
}



signed main()
{
    int T=1;
    cin.tie(0)->sync_with_stdio(false);
    cin>>T;
    //init();
    while(T--) 
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
5 6
1 2 4
1 3 2
2 3 0
3 4 1
4 5 1
5 2 1
4 4
1 2 4
1 3 6
1 4 8
4 2 1000000
3 3
1 2 100
2 1 10
2 3 1000

output:

5
18
1100

result:

ok 3 number(s): "5 18 1100"

Test #2:

score: -100
Time Limit Exceeded

input:

50000
4 5
2 4 998973548
2 3 501271695
4 1 778395982
1 4 32454891
1 2 757288934
4 5
1 4 720856669
2 3 665098951
3 4 407461517
2 1 866914401
1 2 457859826
4 5
1 2 75288664
1 4 624893594
3 2 458973866
2 4 769074655
2 3 834773751
4 5
2 3 237060634
2 4 297307882
3 4 200383586
1 2 42856502
3 1 16574713
4 ...

output:


result: