提出 #2095014
ソースコード 拡げる
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++) #define all(c) begin(c),end(c) const ll INF = ll(1e16); const ll mod = ll(1e9 + 7); const int MAX_E = 2000; const int MAX_V = 1000; struct edge { int from, to; ll cost; }; edge es[MAX_E]; ll d[MAX_V]; int V, E; //s番目の頂点から各頂点への最短距離 void bellman_ford(int s) { for (int i = 0; i < V; i++)d[i] = INF; d[s] = 0; while (1) { bool update = false; for (int i = 0; i < E; i++) { edge e = es[i]; if (d[e.from] != INF&&d[e.to] > d[e.from] + e.cost) { d[e.to] = d[e.from] + e.cost; update = true; } } if (!update)break; } } bool find_negative_loop() { memset(d, 0, sizeof(d)); for (int i = 0; i < V; i++) { for (int j = 0; j < E; j++) { edge e = es[j]; if (d[e.to] > d[e.from] + e.cost) { d[e.to] = d[e.from] + e.cost; if (i == V - 1)return true; } } } return false; } int main() { cin >> V >> E; rep(i, E) { int a, b, c; cin>>a>>b>>c; es[i].from = --a; es[i].to = --b; es[i].cost = -c; } if (find_negative_loop())cout << "inf" << endl; else { bellman_ford(0); cout << -d[V-1] << endl; } return 0; }
提出情報
提出日時 | |
---|---|
問題 | D - Score Attack |
ユーザ | agis |
言語 | C++14 (GCC 5.4.1) |
得点 | 0 |
コード長 | 1356 Byte |
結果 | WA |
実行時間 | 7 ms |
メモリ | 256 KB |
ジャッジ結果
セット名 | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
得点 / 配点 | 0 / 0 | 0 / 400 | ||||||
結果 |
|
|
セット名 | テストケース |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
ケース名 | 結果 | 実行時間 | メモリ |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 2 ms | 256 KB |
subtask_1_10.txt | AC | 1 ms | 256 KB |
subtask_1_11.txt | AC | 2 ms | 256 KB |
subtask_1_12.txt | AC | 5 ms | 256 KB |
subtask_1_13.txt | AC | 1 ms | 256 KB |
subtask_1_14.txt | AC | 4 ms | 256 KB |
subtask_1_15.txt | AC | 7 ms | 256 KB |
subtask_1_16.txt | AC | 1 ms | 256 KB |
subtask_1_17.txt | AC | 1 ms | 256 KB |
subtask_1_18.txt | AC | 3 ms | 256 KB |
subtask_1_19.txt | AC | 4 ms | 256 KB |
subtask_1_2.txt | AC | 3 ms | 256 KB |
subtask_1_20.txt | AC | 1 ms | 256 KB |
subtask_1_21.txt | AC | 3 ms | 256 KB |
subtask_1_22.txt | AC | 5 ms | 256 KB |
subtask_1_23.txt | WA | 1 ms | 256 KB |
subtask_1_24.txt | AC | 4 ms | 256 KB |
subtask_1_25.txt | WA | 2 ms | 256 KB |
subtask_1_26.txt | AC | 3 ms | 256 KB |
subtask_1_27.txt | WA | 4 ms | 256 KB |
subtask_1_3.txt | AC | 3 ms | 256 KB |
subtask_1_4.txt | AC | 3 ms | 256 KB |
subtask_1_5.txt | AC | 2 ms | 256 KB |
subtask_1_6.txt | AC | 4 ms | 256 KB |
subtask_1_7.txt | AC | 3 ms | 256 KB |
subtask_1_8.txt | AC | 3 ms | 256 KB |
subtask_1_9.txt | AC | 1 ms | 256 KB |