結果

問題 No.468 役に立つ競技プログラミング実践編
ユーザー yuppe19 😺
提出日時 2016-12-18 00:35:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,401 bytes
コンパイル時間 999 ms
コンパイル使用メモリ 86,548 KB
実行使用メモリ 814,948 KB
最終ジャッジ日時 2024-12-14 07:17:32
合計ジャッジ時間 19,785 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 7 WA * 14 MLE * 10
other AC * 5 MLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:28:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:31:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |     int a, b, c; scanf("%d%d%d", &a, &b, &c);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
using i64 = long long;

struct edge {
  int to, cost;
};

int n, m;

vector<vector<bool>> prev2;
vector<bool> on_path;

void rec(int i) {
  if(i == 0) { on_path[i] = true; return; }
  if(on_path[i]) { return; }
  on_path[i] = true;
  for(int j=0; j<n; ++j) {
    if(prev2[i][j]) { rec(j); }
  }
}

int main(void) {
  constexpr int inf = 0;
  scanf("%d%d", &n, &m);
  vector<vector<edge>> G(n, vector<edge>()); // G[n][]
  for(int i=0; i<m; ++i) {
    int a, b, c; scanf("%d%d%d", &a, &b, &c);
    G[a].push_back(edge({b, c}));
  }
  vector<int> cost(n, inf); // cost[n]
  prev2.assign(n, vector<bool>(n, false));
  cost[0] = 0;
  queue<pair<int, int>> que;
  // コスト、点番号
  que.emplace(0, 0);
  while(!que.empty()) {
    int _, v; tie(_, v) = que.front(); que.pop();
    for(edge e : G[v]) {
      if(cost[e.to] < cost[v] + e.cost) {
        cost[e.to] = cost[v] + e.cost;
        que.emplace(-cost[e.to], e.to);
        for(int i=0; i<n; ++i) { prev2[e.to][i] = false; }
        prev2[e.to][v] = true;
      } else if(cost[e.to] == cost[v] + e.cost) {
        prev2[e.to][v] = true;
      }
    }
  }
  int res = cost[n-1];
  on_path.assign(n, false);
  rec(n-1);
  int cnt = 0;
  for(int i=0; i<n; ++i) {
    if(!on_path[i]) { ++cnt; }
  }
  printf("%d %d/%d\n", res, cnt, n);
  return 0;
}
0