Submission #377274

#	Time	Username	Problem	Language	Result	Execution time	Memory
377274		practice101	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	408 ms	35700 KiB

commuter_pass

#include<bits/stdc++.h>
/*
Created By Tornado2004
*/
using namespace std;

#define debug(x) cout << '[' << #x << " is: " << x << "] " << endl;
#define imod(a , n) (a % n + n ) % n

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
#define inF freopen("marathon.in","r",stdin );
#define outF freopen("marathon.out" , "w" , stdout ) ;
#define sor(v) sort(v.begin() , v.end());
#define print(v) for(auto f : v ) cout << f << " " ;
#define rsor(v) sort(v.rbegin() , v.rend());
#define rev(v) reverse(v.begin() , v.end());
#define scan(v)for(auto &it : v)cin >> it ;

#define ll long long
#define logar(x , y) log(x) / log(y)
#define int ll
#define pii pair<int , int >
const int N = 1e5 + 5  , K = 11 , M = N * 4 ;
const ll MOD = 1e9 + 7   , oo = 1e9 , OO = 1e18 , mod = MOD ;
const double pi = acos(-1) , eps = 1e-6 ;

//37
// (a ^ b / c ) % mod = (a ^ b ) % MOD * (c ^ (mod - 2)) % mod
// ريتني اعدم المود
int di[] = {0 , 0 , 1 , -1};
int dj[] = {1 , -1 , 0 , 0};

int dis[N];
vector<pair<int , int > > adj[N];
int par[N];


int dijkstra(int s , int e){
    memset(dis , '?' , sizeof dis);

    dis[s] = 0 ;

    priority_queue<pair<int , int > ,vector<pair<int , int > > ,  greater<pair<int , int > > > q ;


    q.push({0 , s});


    while(q.size()){
        auto tp = q.top();//cout << tp.first << " " << tp.second << endl ;
        q.pop();

        if(dis[tp.second] < tp.first)continue ;
        if(tp.second == e)return tp.first ;


        for(auto f : adj[tp.second]){
            int nc = tp.first + f.second ;
           // debug(f.first);
           // debug(nc);
            if(dis[f.first] > nc){//cout << "here" << endl ;
                par[f.first] = tp.second ;
                q.push({nc , f.first});
                dis[f.first] = nc ;

            }

        }
    }


}

map<pair<int , int > , int > mp ;


void HappyBirthday(int u){
    if(par[u] == -1)return ;

    mp[{u , par[u]}] ++ ;
    mp[{par[u] , u}] ++ ;

    HappyBirthday(par[u]);

}
int32_t main()
{   //inF;
   // inF;outF;
    fastio;
   int n , m;
   cin >> n >> m ;

   int s , t , u , v ;
   cin >> s >> t >> u >> v ;
    while(m--){

        int a , b , c ;
        cin >> a >> b >> c ;

        adj[a].push_back({b , c});
        adj[b].push_back({a , c});

    }
    par[s] = -1 ;

    dijkstra(s , t);

    HappyBirthday(t);


    for(int i = 1 ; i <= n ; i++){
        for(auto &f : adj[i]){
            if(mp.count({i , f.first}))f.second = 0 ;


        }
    }

    cout << dijkstra(u , v);

}

/*🎂🎁🎉👑
HAPPY TORNADO`S BIRTHDAY 💜💜
*/

Compilation message (stderr)

commuter_pass.cpp: In function 'long long int dijkstra(long long int, long long int)':
commuter_pass.cpp:43:96: warning: control reaches end of non-void function [-Wreturn-type]
   43 |     priority_queue<pair<int , int > ,vector<pair<int , int > > ,  greater<pair<int , int > > > q ;
      |                                                                                                ^

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