Submission #764776

#	Time	Username	Problem	Language	Result	Execution time	Memory
764776		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	838 ms	39476 KiB

commuter_pass

/******************
tree-bends-in-youth
//22///06///2023///
******************/
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
const ll N = 1e5 + 1;
const ll INF = 1e17;
const ll MOD = 1e9 + 7;
vector <int> g[N];
map <pair<int,int>,int> cnt;
ll d[N];
int a[N];
void solve(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        d[i] = INF;
    }
    int s,t,u,o;
    cin >> s >>t >>u >> o;
    for(int i = 1;i <= m;i++){
        int x,y,w;
        cin >> x >> y >> w;
        cnt[{x,y}] = w;
        cnt[{y,x}] = w;
        g[x].pb(y);
        g[y].pb(x);
    }
    set <pair<int,int> > q;
    d[s] = 0;
    q.insert({d[s],s});
    while(!q.empty()){
        int v = q.begin() -> second;
        q.erase(q.begin());
        for(auto to : g[v]){
            if(d[to] > d[v] + cnt[{v,to}]){
                q.erase({d[to],to});
                d[to] = d[v] + cnt[{v,to}];
                a[to] = v;
                q.insert({d[to],to});
            }
        }
    }
    vector <int> l;
    int x = t;
    while(x != 0){
        l.pb(x);
        x = a[x];
    }
    for(int i = 0;i < l.size() - 1;i++){
        cnt[{l[i],l[i + 1]}] = 0;
        cnt[{l[i + 1],l[i]}] = 0;
    }
    for(int i = 1;i <= n;i++){
        d[i] =INF;
    }
    d[u] = 0;
    q.insert({d[u],u});
    while(!q.empty()){
        int v = q.begin() -> second;
        q.erase(q.begin());
        for(auto to : g[v]){
            if(d[to]  > d[v] + cnt[{v,to}]){
                q.erase({d[to],to});
                d[to] = d[v] + cnt[{v,to}];
                q.insert({d[to],to});
            }
        }
    }
    cout  << d[o];
}
main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	//freopen("censor.in","r",stdin);
	//freopen("censor.out","w",stdout);
    ll T = 1;
    //cin >> T;
    for(ll i = 1;i <= T;i++){
      //  cout << "Case " << i << ":\n";
        solve();
    }
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i = 0;i < l.size() - 1;i++){
      |                   ~~^~~~~~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main () {
      | ^~~~

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45