結果

問題 No.1 道のショートカット
ユーザー Rumain831
提出日時 2025-05-12 00:09:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,223 bytes
コンパイル時間 1,219 ms
コンパイル使用メモリ 94,280 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-12 00:09:50
合計ジャッジ時間 2,822 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 33 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<algorithm>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using tu = tuple<int, int, int>;

int main(void){
  int n, c, v; cin >> n >> c >> v;
  vector<int> s(v), t(v), y(v), m(v);
  for(int i=0; i<v; i++) cin >> s[i], s[i]--;
  for(int i=0; i<v; i++) cin >> t[i], t[i]--;
  for(int i=0; i<v; i++) cin >> y[i];
  for(int i=0; i<v; i++) cin >> m[i];
  vector<vector<vector<P>>> to(n, vector<vector<P>>(n));
  for(int i=0; i<v; i++){
    to[s[i]][t[i]].emplace_back(m[i], y[i]);
    //to[t[i]][s[i]]=min(to[t[i]][s[i]], {m[i], y[i]});
  }
  vector<P> dist(n, {1e8, 1e8});
  priority_queue<tu, vector<tu>, greater<tu>> dij;
  dij.emplace(0, 0, 0);
  dist[0]={0, 0};
  while(dij.size()){
    auto [time, cost, idx]=dij.top(); dij.pop();
    if(dist[idx]!=P(time, cost)) continue;
    for(int i=0; i<n; i++){
      for(auto [dt, dc]:to[idx][i]){
        if(cost+dc>c) continue;
        if(dist[i]>P(time+dt, cost+dc)){
          dist[i]=P(time+dt, cost+dc);
          dij.emplace(time+dt, cost+dc, i);
        }
      }
    }
  }
  if(dist[n-1].second<=c) cout << dist[n-1].first << endl;
  else cout << -1 << endl;
  return 0;
}
0