Submission #1280540


Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cassert>
#include <queue>
#define int long long
using namespace std;

int INF = 1e+15;
int n, m;
vector<int> et[1000];
vector<int> ec[1000];

vector<int> rev_et[1000];
bool cango[1000];

int dp[1000];

void make() {	//到達可能性
	queue<int> que;
	cango[n - 1] = true;
	que.push(n - 1);
	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (int i = 0; i < rev_et[v].size(); i++) {
			if (cango[rev_et[v][i]]) continue;
			cango[rev_et[v][i]] = true;
			que.push(rev_et[v][i]);
		}
	}
}

signed main() {
	int i;
	
	cin >> n >> m;
	for (i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		et[a].push_back(b);
		ec[a].push_back(c);
		rev_et[b].push_back(a);
	}
	
	make();
	
	for (i = 0; i < n; i++) { dp[i] = -INF; }
	
	queue<int> que;
	que.push(0); dp[0] = 0;
	
	int loop = 0;
	while(!que.empty()) {
		int v = que.front(); que.pop();
		for (int i = 0; i < et[v].size(); i++) {
			if (!cango[et[v][i]] || dp[et[v][i]] >= dp[v] + ec[v][i]) continue;
			dp[et[v][i]] = dp[v] + ec[v][i];
			que.push(et[v][i]);
		}
		loop++;
		if (loop >= 5000000) {
			break;
		}
	}
	
	if (loop >= 5000000) { cout << "inf" << endl; }
	else { cout << dp[n - 1] << endl; }
	
	return 0;
}

Submission Info

Submission Time
Task D - Score Attack
User startcpp
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1356 Byte
Status AC
Exec Time 330 ms
Memory 104552 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
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
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 384 KB
sample_02.txt AC 43 ms 384 KB
sample_03.txt AC 1 ms 384 KB
subtask_1_1.txt AC 2 ms 384 KB
subtask_1_10.txt AC 330 ms 104552 KB
subtask_1_11.txt AC 58 ms 384 KB
subtask_1_12.txt AC 144 ms 6148 KB
subtask_1_13.txt AC 1 ms 384 KB
subtask_1_14.txt AC 55 ms 384 KB
subtask_1_15.txt AC 179 ms 8580 KB
subtask_1_16.txt AC 1 ms 256 KB
subtask_1_17.txt AC 1 ms 384 KB
subtask_1_18.txt AC 2 ms 384 KB
subtask_1_19.txt AC 3 ms 384 KB
subtask_1_2.txt AC 2 ms 384 KB
subtask_1_20.txt AC 1 ms 384 KB
subtask_1_21.txt AC 2 ms 384 KB
subtask_1_22.txt AC 3 ms 384 KB
subtask_1_23.txt AC 1 ms 256 KB
subtask_1_24.txt AC 3 ms 384 KB
subtask_1_25.txt AC 2 ms 384 KB
subtask_1_26.txt AC 2 ms 384 KB
subtask_1_27.txt AC 2 ms 384 KB
subtask_1_3.txt AC 2 ms 384 KB
subtask_1_4.txt AC 2 ms 384 KB
subtask_1_5.txt AC 47 ms 384 KB
subtask_1_6.txt AC 47 ms 384 KB
subtask_1_7.txt AC 2 ms 384 KB
subtask_1_8.txt AC 2 ms 384 KB
subtask_1_9.txt AC 1 ms 384 KB