Submission #833295

#	Time	Username	Problem	Language	Result	Execution time	Memory
833295		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	249 ms	24452 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, s, t, u, v, a, b, c, now;
vector<pair<int,int>> edges[100002];
map<pair<int,int>, ll> rem;
bool kwek=false;
const ll INF=1e18;
void dijkstra(){
    vector<ll> dist(n+2, INF);
    vector<bool> vis(n+2, false);
    vector<int> pred(n+2, -1);
    priority_queue<pair<ll,pair<int,int>>, vector<pair<ll,pair<int,int>>>, greater<pair<ll,pair<int,int>>>> pq;

    dist[s]=0;
    pq.push({0, {0, s}});
    while(!pq.empty()){
        now=pq.top().second.second;
        pq.pop();
        if(!vis[now]){
            vis[now]=true;
            for(auto i: edges[now]){
                if(dist[i.first] >= dist[now] + i.second){
                    dist[i.first]=dist[now]+i.second;
                    pred[i.first]=now;
                    pq.push({dist[i.first], {rem[{now, i.first}], i.first}});
                }
            }
        }
    }
    vector<pair<int,int>> ubah;
    vector<int> temp;
    now=t;
    while(pred[now] != -1){
        // cout<<now<<"->"<<pred[now]<<"\n";
        ubah.push_back({now, pred[now]});
        ubah.push_back({pred[now], now});
        now=pred[now];
    }
    sort(ubah.begin(), ubah.end());
    int k;
    for(int i=0; i<ubah.size(); i++){
        k=0;
        now=ubah[i].first;
        temp.push_back(ubah[i].second);
        while((i+1)<n && ubah[i+1].first == now){
            temp.push_back(ubah[i+1].second);
            i++;
        }
        for(int j=0; j<edges[now].size(); j++){
            if(temp[k] == edges[now][j].first){
                edges[now][j].second=0;
                k++;
            }
        }
        temp.clear();
    }
}
void dijkstra2(){
    vector<ll> dist(n+2, INF);
    vector<bool> vis(n+2, false);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    vector<int> pred(n+2, -1);
    dist[u]=0;
    pq.push({0, u});
    while(!pq.empty()){
        now=pq.top().second;
        pq.pop();
        if(!vis[now]){
            vis[now]=true;
            for(auto i: edges[now]){
                if(dist[i.first] > dist[now] + i.second){
                    dist[i.first]=dist[now]+i.second;
                    pred[i.first]=now;
                    pq.push({dist[i.first], i.first});
                }
            }
        }
    }
    now=v;
    if(kwek) cout<<dist[v]<<"\n";
    else{
        while(pred[now] != -1){
            // cout<<now<<"->"<<pred[now]<<"   "<<dist[now]-dist[pred[now]]<<"\n";
            rem[{now, pred[now]}]=(ll)1e9-(dist[now]-dist[pred[now]]);
            rem[{pred[now], now}]=(ll)1e9-(dist[now]-dist[pred[now]]);
            now=pred[now];
        }
    }
    kwek=true;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=0; i<m; i++){
        cin>>a>>b>>c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }
    dijkstra2();
    dijkstra();
    dijkstra2();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra()':
commuter_pass.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0; i<ubah.size(); i++){
      |                  ~^~~~~~~~~~~~
commuter_pass.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j=0; j<edges[now].size(); j++){
      |                      ~^~~~~~~~~~~~~~~~~~

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