Submission #1281232

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
const int M = 2010;
typedef long long LL;

int n, m;

struct Edge{
	int to, id;
	Edge(){}
	Edge(int to, int id):to(to),id(id){}
};
vector<Edge> V[N];
vector<int> G[N];
bool vis_edge[M];
bool ok[N];
int dis[M];

void init(){
	for(int i=1; i<=n; i++){
		ok[i] = 0;
	}
	queue<int> Q;
	Q.push(n);
	ok[n] = 1;
	while(!Q.empty()){
		int x = Q.front(); Q.pop();
		for(int i=0; i<G[x].size(); i++){
			int j = G[x][i];
			if(!ok[j]){
				ok[j] = 1;
				Q.push(j);
			}
		}
	}
}

LL dp[N], ed[M];
bool vis[N];

struct Node{
	int to;
	LL d;
	Node(){}
	Node(int to, LL d):to(to),d(d){}
	bool operator < (const Node &A)const{
		return d > A.d;
	}
};

int cnt[N];

void solve(){
	LL ans;
	bool flag= 0;
	for(int i=1; i<=n; i++){
		vis[i] = 0;
		cnt[i] = 0;
	}
	priority_queue<Node> Q;
	Q.push(Node(1, 0));
	while(!Q.empty()){
		Node nd = Q.top(); Q.pop();
		if(!vis[nd.to]){
			vis[nd.to] = 1;
		} else {
			if(nd.d < dp[nd.to])	continue;
		}
		if(nd.to == n){
			if(!flag){
				ans = nd.d;
				flag = 1;
			}
			ans = max(ans, nd.d);
		}
		dp[nd.to] = nd.d;
		cnt[nd.to]++;
		if(cnt[nd.to] > n){
			puts("inf");
			return;
		}
		for(int i=0; i<V[nd.to].size(); i++){
			int j = V[nd.to][i].to;
			int k = V[nd.to][i].id;
			if(!ok[j])	continue;
			if(!vis[j] || dp[j] < nd.d + dis[k]){
				vis[j] = 1;
				dp[j] = nd.d + dis[k];
				Q.push(Node(j, dp[j]));
			}
		}
	}
	printf("%lld\n", ans);
}

int main(){
	int x, y, z;
	while(~scanf("%d %d", &n, &m)){
		for(int i=1; i<=n; i++){
			V[i].clear();
			G[i].clear();
		}
		for(int i=1; i<=m; i++){
			scanf("%d %d %d", &x, &y, dis+i);
			V[x].push_back(Edge(y, i));
			G[y].push_back(x);
		}
		init();
		solve();
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:106:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &x, &y, dis+i);
                                    ^

Judge Result