QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318777#7991. 最小环Delay_for_five_minutesTL 135ms51408kbC++203.6kb2024-01-31 20:18:242024-01-31 20:18:25

Judging History

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

  • [2024-01-31 20:18:25]
  • 评测
  • 测评结果:TL
  • 用时:135ms
  • 内存:51408kb
  • [2024-01-31 20:18:24]
  • 提交

answer


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n , m;
map<int , pair<ll,ll> > E[300005];
const ll inf = 1e18 + 1;
void adde(int u,int v,ll w) {
    if(E[u].count(v)) {
        E[u][v].first = min(E[u][v].first , (ll)w) ;
    }
    else {
        E[u][v] = {w , inf} ;
    }
    if(E[v].count(u)) {
        E[v][u].second = min(E[v][u].second , (ll)w) ;
    }
    else {
        E[v][u] = {inf , w};
    }
}
void remov(int u,int v) {
    E[u].erase(v) ;
}
bool in[300005];

vector<pair<int,int> > Ed[6005];

ll ans = 1e18;
ll dis[300005];
int use[300005];
void run(int u) {
    dis[u] = 0;use[u] = u;
    priority_queue<pair<int,int> > pq;
    pq.push({0 , u}) ;
    int id = u;
    while(pq.size()) {
        int u = pq.top().second ; pq.pop() ;
        for(auto [v,w] : Ed[u]) {
            if(use[v] != id || dis[v] > dis[u] + w) {
                use[v] = id;
                dis[v] = dis[u] + w;
                pq.push({-dis[v] , v}) ;
            }
            if(v == id) {
                ans = min(ans , w + dis[u]) ;
            }
        }
    }

}
int main() {
    //freopen("in.txt","r",stdin) ;
    // freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    cin >> n >> m;
    for(int i = 1;i <= m;i++) {
        int u , v , w;cin >> u >> v >> w;
        if(u == v) {ans = min(ans , (ll)w) ; continue ;}
        adde(u , v , w);
    }
    if(n == 1) {
        if(ans > (1e17)) ans = -1;
        cout << ans ; return 0;
    }
    queue<int> q;int lft = n;
    for(int i = 1;i <= n;i++) {
        if(E[i].size() <= 2) in[i] = 1 , q.push(i);
    }
    // puts("OK") ;
    while(q.size() && lft > 1) {
        lft--;
        auto u = q.front() ; q.pop() ;
        // printf("%d\n",u);
        if(E[u].size() == 1) {
            int v = E[u].begin()->first ;
            // printf("%lld %lld\n",E[u][v].first , E[u][v].second) ;
            if(E[u][v].first != inf && E[u][v].second != inf) {
                ans = min(ans , E[u][v].first + E[u][v].second) ;
            }
            E[v].erase(u) ; E[u].clear() ;
            if(E[v].size() <= 2 && !in[v]) {in[v] = 1;q.push(v) ;}
        }
        else {
            // printf("E %d\n",E[u].size()) ;
            auto it1 = E[u].begin();
            auto it2 = it1;
            it2++;
            remov(it1->first , u) ;
            remov(it2->first , u) ;
            // printf("%lld %lld , %lld %lld\n",it1->second.first , it1->second.second , it2->second.first , it2->second.second) ;
            adde(it1->first , it2->first , min(inf , it1->second.second + it2->second.first)) ;
            adde(it2->first , it1->first , min(inf , it1->second.first + it2->second.second)) ;
            if(it1->second.first != inf && it1->second.second != inf) ans = min(ans , it1->second.first + it1->second.second) ;
            if(it2->second.first != inf && it2->second.second != inf) ans = min(ans , it2->second.first + it2->second.second) ;
            if(E[it1->first].size() <= 2 && !in[it1->first]) {in[it1->first] = 1;q.push(it1->first );}
            if(E[it2->first].size() <= 2 && !in[it2->first]) {in[it2->first] = 1;q.push(it2->first );}
            E[u].clear() ;
        }
    }
    // puts("OK") ;
    for(int i = 1;i <= n;i++) {
        if(!in[i]) {
            for(auto [v , t] : E[i]) {
                if(t.first != inf) Ed[i].push_back({v , t.first}) ;
            }
        }
    }
    for(int i = 1;i <= n;i++) {
        if(!in[i]) run(i);
    }
    if(ans == (1000000000000000000)) ans = -1;
    cout << ans << '\n' ;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 21360kb

input:

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

output:

7

result:

ok single line: '7'

Test #2:

score: 0
Accepted
time: 0ms
memory: 18248kb

input:

1 0

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 4ms
memory: 19680kb

input:

1 1
1 1 1

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 135ms
memory: 51408kb

input:

258420 258419
33061 33062 767169384
212916 212917 1741339
229881 229882 896760805
173467 173468 273055172
233189 233190 800433307
10157 10158 126766550
174605 174606 552176083
224030 224031 886617880
229102 229103 783848581
67588 67589 510826095
233648 233649 879695751
214453 214454 867104578
153140...

output:

-1

result:

ok single line: '-1'

Test #5:

score: -100
Time Limit Exceeded

input:

248016 248896
82688 82755 592665252
202847 203260 294408121
26821 28237 269132335
150967 152178 3125829
246069 247390 29492546
7470 7673 55843492
33975 35414 442802995
28451 28948 193736988
34484 34637 84441058
60168 60309 501991354
79579 79844 26854803
239672 239706 111702667
73548 73658 149840530
...

output:


result: