Submission #6821035

---

Source Code Expand

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=5e3+2;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int head[N],dis[N],vis[N],QAQ[N],cnt,n,m,p;
struct Edge {int nxt,w,to;} G[N<<1]; 
inline void add(int u,int v,int w) {
	G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].w=w,head[u]=cnt;
}
inline void Spfa() {
	memset(dis,127,sizeof(dis));
    int inf=-(1e9+7);
	deque<int> q;q.push_back(1),dis[1]=0,vis[1]=true;
	while(!q.empty()) {
		int u=q.front();q.pop_front();++QAQ[u],vis[u]=false;
        if(QAQ[u]>=n) dis[u]=inf;
		for(int i=head[u];i;i=G[i].nxt) {
			int v=G[i].to;
			if(dis[u]+G[i].w<dis[v]&&QAQ[v]<n) {
				dis[v]=dis[u]+G[i].w;     
			    if(vis[v]==false)
				    v<q.front()?q.push_front(v):q.push_back(v),vis[v]=true; 
		    }
		}
	}
}

int main() {
    // freopen("G.in","r",stdin);
    // freopen("G.out","w",stdout);
    IN(n),IN(m),IN(p);
    for(int i=1,a,b,c;i<=m;++i)
        IN(a),IN(b),IN(c),add(a,b,-(c-p));
    Spfa();
    if(dis[n]<-5e8) puts("-1");
    else printf("%d\n",(dis[n]<0)?-dis[n]:0);
    return 0;
}

Submission Info

Judge Result