Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #1284461

Source Code Expand

Copy
```#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#include <queue>

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;
struct Edge {
int a, b, c;
Edge (int a, int b, int c) : a(a), b(b), c(c) {}
Edge () {}
};

int main () {
int N, M;
cin >> N >> M;
vector<vector<int>> G;
G.resize(N);
vector<Edge> edges(M);

REP (i, 0, M) {
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
G[b].push_back(a);
edges[i].a = a;
edges[i].b = b;
edges[i].c = -c;
}

queue<int> q;
vector<bool> isAccess(N, false);
q.push(N - 1);
while (q.size()) {
int v = q.front();
q.pop();
if (isAccess[v]) continue;
isAccess[v] = true;
REP (i, 0, G[v].size()) {
q.push(G[v][i]);
}
}

const lli inf = 1LL << 60;
vector<lli> dis(N, inf);
dis[0] = 0;
REP (i, 0, 2 * N) {
for (auto edge : edges) {
int from = edge.a;
int to = edge.b;
if (dis[from] + edge.c < dis[to]) {
if (i >= N - 1 && (isAccess[to] || isAccess[from])) {
cout << "inf" << endl;
return 0;
}
dis[to] = dis[from] + edge.c;
}
}
}
cout << -dis[N - 1] << endl;
return 0;
}
```

#### Submission Info

Submission Time 2017-05-13 22:11:49+0900 D - Score Attack commy C++14 (GCC 5.4.1) 400 1534 Byte AC 12 ms 384 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
 AC × 3
 AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB