結果

問題 No.2805 Go to School
ユーザー gyozasukisuki
提出日時 2024-07-12 23:58:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 275 ms / 2,000 ms
コード長 4,756 bytes
コンパイル時間 2,506 ms
コンパイル使用メモリ 209,280 KB
最終ジャッジ日時 2025-02-22 05:54:30
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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;
  
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0