Submission #1311616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311616		filip1111	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	1339 ms	327680 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = long long;
const int N = 1e5 + 99;
vector<pair<int,int>>tab[N];
const ll inf = 1e18;
ll odl[N];

ll dijkstra(int a, int b, int n){
    for(int i = 0; i < n+ 9; ++i)odl[i] = inf;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0,a});
    while(!pq.empty()){
        auto[x,v] = pq.top();
        pq.pop();
        if(odl[v] <= x)continue;
        odl[v] = x;
        for(auto [u,y] : tab[v]){
            pq.push({x+y,u});
        }
    }
    return odl[b];
}
bool vis[N];
map<pair<int,int>,bool>M;

void dfs(int v){
    if(vis[v])return;
    vis[v] = 1;
    ll mini = inf;
    for(auto [u,y] : tab[v]){
        mini = min(mini, odl[u] + y);
    }
    for(auto [u, y] : tab[v]){
        if(mini == odl[u] + y){
            dfs(u);
            M[{u,v}]=1;
            // M[{v,u}]=1;
        }
    }
}
int main(){
    int n, m;
    cin >> n >> m;
    int S,T, U, V;
    cin >> S >> T >> U >> V;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        tab[a].push_back({b,c});
        tab[b].push_back({a,c});
    }
    ll oo = dijkstra(S,T,n);
    dfs(T);
    for(int i = 1; i <= n; i++){
        for(auto &[v,x] : tab[i]){
            if(M[{i,v}])x = 0;
            else if(M[{v,i}]) x = inf ;
        }
    }
    ll ooo = dijkstra(U,V,n);
     for(int i = 1; i <= n; i++){
        for(auto &[v,x] : tab[i]){
            if(M[{v,i}])x = 0;
            else if(M[{i,v}]) x = inf ;
        }
    }
    ll oooo = dijkstra(U,V, n);
    assert(min(ooo,oooo) >= 0);
    cout << min(ooo,oooo) << endl;
    
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:59:35: warning: overflow in conversion from 'll' {aka 'long long int'} to 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   59 |             else if(M[{v,i}]) x = inf ;
      |                                   ^~~
commuter_pass.cpp:66:35: warning: overflow in conversion from 'll' {aka 'long long int'} to 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   66 |             else if(M[{i,v}]) x = inf ;
      |                                   ^~~

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