洛谷P1938 找工就业

传送门啦

这个题本质就是跑一边最长路，重点就是在怎么建图上。

我们可以把点权放到边权上面，即将每一个边的终点点权当做这个边的边权，这个题里就是将工钱 $ d $ 当做边权。

如果这一条边需要坐飞机才能到达，我们就可以将 $ d-w $ 当做边权进行建图，这个时候你发现了什么？？

你会发现 $ d-w $ 可能是个负值，所以我们跑最长路的时候就不能用 $ dijk $了。

最后我们就考虑怎么判断无限挣钱的情况了，那个情况下就是出现了环，可以不断走。所以我们开一个数组，记录一下每条最长路上点的个数，只要大于 $ c $ ，就是说明我们走了一个环，就打一个标记，判断一下输出 $ -1 $

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int maxn = 2000;

inline int read(){

	char ch = getchar();

	int f = 1 , x = 0;

	while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}

	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}

	return x * f;

}

int d,p,c,f,s,u,v,w;

struct Edge{

	int to,from,val,next;

}edge[maxn << 1];

int head[maxn],tot;

int dis[maxn],ans,go[maxn];

bool flag,vis[maxn];

void add(int u,int v,int w){

	edge[++tot].from = u;

	edge[tot].to = v;

	edge[tot].val = w;

	edge[tot].next = head[u];

	head[u] = tot;

}

struct node{

	int u,dist;

	bool operator < (const node &x) const{

		return dist > x.dist;

	}

};

void spfa(int s){

	queue<int> q;

	q.push(s);

	dis[s] = d; vis[s] = true;

	while(!q.empty()){

		int cur = q.front();

		q.pop(); vis[cur] = false;

		for(int i=head[cur];i;i=edge[i].next){

			int v = edge[i].to;

			if(dis[v] < dis[cur] + edge[i].val){

				dis[v] = dis[cur] + edge[i].val;

				go[v] = go[u] + 1;

				if(go[v] > c){

					flag = true;

					return;

				}

				if(!vis[v]){

					q.push(v);

					vis[v] = true;

				}

			}

		}

	}

}

int main(){

	d = read(); p = read(); c = read(); f = read(); s = read();

	for(int i=1;i<=p;i++){

		u = read(); v = read();

		add(u , v , d);

	}

	for(int i=1;i<=f;i++){

		u = read(); v = read(); w = read();

		add(u , v , d-w);

}

	spfa(s);

	if(flag == 1){printf("-1\n");return 0;}

	for(int i=1;i<=c;i++)

		ans = max(ans , dis[i]);

	printf("%d\n",ans);

	return 0;

}