結果

問題 No.2805 Go to School
ユーザー gyozasukisukigyozasukisuki
提出日時 2024-07-12 23:58:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 304 ms / 2,000 ms
コード長 4,756 bytes
コンパイル時間 2,991 ms
コンパイル使用メモリ 217,616 KB
実行使用メモリ 26,768 KB
最終ジャッジ日時 2024-07-16 01:41:22
合計ジャッジ時間 7,797 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 83 ms
18,304 KB
testcase_05 AC 116 ms
14,228 KB
testcase_06 AC 69 ms
9,568 KB
testcase_07 AC 55 ms
9,292 KB
testcase_08 AC 91 ms
14,448 KB
testcase_09 AC 71 ms
9,460 KB
testcase_10 AC 55 ms
9,156 KB
testcase_11 AC 304 ms
23,724 KB
testcase_12 AC 171 ms
15,832 KB
testcase_13 AC 255 ms
19,864 KB
testcase_14 AC 31 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 104 ms
11,872 KB
testcase_19 AC 73 ms
9,500 KB
testcase_20 AC 169 ms
16,432 KB
testcase_21 AC 264 ms
23,144 KB
testcase_22 AC 106 ms
12,100 KB
testcase_23 AC 162 ms
15,620 KB
testcase_24 AC 163 ms
15,260 KB
testcase_25 AC 46 ms
9,328 KB
testcase_26 AC 177 ms
26,768 KB
testcase_27 AC 98 ms
19,424 KB
testcase_28 AC 10 ms
8,192 KB
testcase_29 AC 16 ms
9,088 KB
testcase_30 AC 51 ms
14,720 KB
testcase_31 AC 82 ms
11,520 KB
testcase_32 AC 112 ms
20,448 KB
testcase_33 AC 179 ms
20,968 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 81 ms
9,828 KB
testcase_37 AC 96 ms
11,520 KB
testcase_38 AC 188 ms
17,652 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/all>
// using namespace atcoder;

const int INF = 1e9;
using ll = long long;
using ull = unsigned long long;
using ullv = vector<ull>;
using inv = vector<int>;
using stv = vector<string>;
using llv = vector<ll>;
using ld = long double;
using pint = pair<int,int>;
#define FOR(i,l,r) for(int i=(int)(l); i<(int)(r); i++)
#define rep(i,r) for(ll i=0; i<(ll)(r); i++)
#define repl(i,r) for(long long i=0; i<(long long)(r); i++)
#define FORl(i,l,r) for(long long i=(long long)(l); i<(long long)(r); i++)
#define INFL (long long)((1LL<<62)-(1LL<<31))
#define pb(x) push_back(x)
#define printVec(x) for(auto s:x) cout << s << " "; cout << endl
#define ALL(x) x.begin(),x.end()

template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
ll floor(ll N, ll d){
    if(d < 0)
        N *= -1, d *= -1;
    
    if(N > 0)
        return N / d;
    else
        return (N+1) / d-1;
}
ll ceil(ll N, ll d)
{
    if(d < 0)
        N *= -1, d *= -1;
    
    if(N > 0)
        return (N - 1) / d + 1;
    else
        return N / d;
}

long long pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret *= x;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x *= x;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//拡張ユークリッド互除法
long long int ext_gcd(long long int a, long long int b, long long int &x, long long int &y)
{
  if (b == 0)
  {
    x = 1;
    y = 0;
    return a;
  }
  long long int q = a / b;
  long long int g = ext_gcd(b, a-q*b, x, y);
  long long int z = x-q*y;
  x = y;
  y = z;
  return g;
}

//aとmは互いに素, a^(-1) mod m
long long int modinv(long long int a, long long int m) 
{
  long long int x, y;
  ext_gcd(a, m, x, y);
  x %= m;
  if (x < 0)
    x += m;
  return x;
}

ll takemod(ll x,ll m){
  ll num = x;
  num %= m;
  if (num < 0)
    num += m;
  return num;
}

const ll MOD = 998244353LL;
ll N;
string S,T;

ll convert(string s){
  reverse(ALL(s));
  ll res = 0;
  rep(i,s.size()){
    if(s[i] == 'B'){
      res += (1LL << i);
    }
  }
  return res;
}

string binary(ll bina){
    string ans = "";
    for (int i = 0; bina>0 ; i++)
    {
        if(bina%2) ans.pb('1');
        else ans.pb('0');
        bina = bina/2;
    }
  reverse(ALL(ans));
  return ans;
}

string contos(ll n){
  string ns = binary(n);
  
  string ans = "";
  
  for (int i = 0; n>0 ; i++)
  {
      if(n%2) ans.pb('B');
      else ans.pb('W');
      n= n/2;
  
  }
  rep(i,N-ns.size()+2) ans.pb('W');
  reverse(ALL(ans));
  return ans;
}


struct Edge{
    ll to;
    ll cost;
};

using Graph = vector<vector<Edge>>;
using P = pair<long, int>;

void dijkstra(const Graph &G, int s, vector<long long> &dis, vector<long long> &prev) {
    int N = G.size();
    // dis.resize(N, INFL);
    // prev.resize(N, -1); // 初期化
    
    priority_queue<P, vector<P>, greater<P>> pq; 
    dis[s] = 0;
    pq.emplace(dis[s], s);
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if (dis[v] < p.first) {
            continue;
        }
        for (auto &e : G[v]) {
            if (dis[e.to] > dis[v] + e.cost) {
                dis[e.to] = dis[v] + e.cost;
                prev[e.to] = v; // 頂点 v を通って e.to にたどり着いた
                pq.emplace(dis[e.to], e.to);
            }
        }
    }
}

int main(){
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // cout << fixed << setprecision(15);

  ll N,M,L,S,E;
  cin >> N >> M >> L >> S >> E;
  Graph G(N,vector<Edge>());
  rep(i,M){
    Edge e;
    ll a,b,t;
    cin >> a >> b >> t;
    a--,b--;
    e.to = b;
    e.cost = t;
    G[a].pb(e);

    e.to = a;
    G[b].pb(e);
  }
  llv T(L);
  rep(i,L){
    cin >> T[i];
    T[i]--;
  }

  
  llv sdis(N,INFL),gdis(N,INFL);
  llv sprev(N,-1),gprev(N,-1);

  dijkstra(G,0,sdis,sprev);
  dijkstra(G,N-1,gdis,gprev);
  // for

  ll ans = INFL;
  for(auto t: T){
    if(!(sdis[t] <= S+E)) continue;
    ll los = 0;
    if(S > sdis[t]) los = S-sdis[t];
    // cout << sdis[t]+los+1LL+gdis[t] << endl;
    chmin(ans,sdis[t]+los+1LL+gdis[t]);
  }
  cout << (ans == INFL ? -1: ans) << endl;
  
}
0