oj.uz

답안 #377274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
377274 2021-03-13T15:51:07 Z practice101 Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 408 ms 35700 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 21684 KB Output is correct
2 Correct 215 ms 19760 KB Output is correct
3 Correct 384 ms 35700 KB Output is correct
4 Incorrect 252 ms 20400 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 25184 KB Output is correct
2 Correct 282 ms 27284 KB Output is correct
3 Correct 253 ms 25692 KB Output is correct
4 Correct 251 ms 27104 KB Output is correct
5 Correct 297 ms 28736 KB Output is correct
6 Correct 408 ms 34292 KB Output is correct
7 Correct 325 ms 35340 KB Output is correct
8 Correct 286 ms 27260 KB Output is correct
9 Correct 270 ms 28560 KB Output is correct
10 Correct 226 ms 24724 KB Output is correct
11 Correct 215 ms 26348 KB Output is correct
12 Correct 382 ms 34928 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 5228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 21684 KB Output is correct
2 Correct 215 ms 19760 KB Output is correct
3 Correct 384 ms 35700 KB Output is correct
4 Incorrect 252 ms 20400 KB Output isn't correct
5 Halted 0 ms 0 KB -