Submission #63286052

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define fi first
#define se second
#define pcnt __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
string zero_padding(int val, int nf){ ostringstream sout;sout << setfill('0') << setw(nf) << val; return sout.str();};
const ld eps = 1e-10;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define fi first
#define se second
#define pcnt __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
string zero_padding(int val, int nf){ ostringstream sout;sout << setfill('0') << setw(nf) << val; return sout.str();};
const ld eps = 1e-10;
const ll INF = 1e18; 
ull mo = 1000000007;
ld PI=asin(1)*2;
//using namespace atcoder;

using TU = tuple<ll,ll,ll>;
int main(){
    ll N,M,X;
    cin >> N >> M >> X;
    vector<vector<ll>> G(N), H(N);
    rep(i,M){
        ll u,v;
        cin >> u >> v;
        u--;v--;
        G[u].push_back(v);
        H[v].push_back(u);
    }
    vector<vector<ll>> d1(N,vector<ll>(2,1e18));
    priority_queue<TU, vector<TU>, greater<TU>> que;
    que.push({0,0,0});
    while(!que.empty()){
        auto [c,v,t] = que.top();
        que.pop();
        //if(d1[v] <= cost) continue;
        if(d1[v][t] != 1e18) continue;
        d1[v][t] = c;
        if(t == 0){
            for(auto& u:G[v]){
                que.push({c+1,u,0});
            }
            for(auto& u:H[v]){
                que.push({c+X+1,u,1});
            }
        }else{
            for(auto& u:G[v]){
                que.push({c+X+1,u,0});
            }
            for(auto& u:H[v]){
                que.push({c+1,u,1});
            }                
        }
    }
    cout << min(d1[N-1][0], d1[N-1][1]) << endl;
}

Submission Info

Judge Result