社区讨论

可以用dij跑最长路吗

P1938[USACO09NOV] Job Hunt S参与者 9已保存回复 17

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
17 条
当前快照
1 份
快照标识符
@mi86m39n
此快照首次捕获于
2025/11/21 09:28
4 个月前
此快照最后确认于
2025/11/21 09:55
4 个月前
查看原帖
RT,题解里好像都是用SPFA的
CPP
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 230,MAXM = 550;

struct node
{
	int p,d;
	node(int _p = 0,int _d = 0) : p(_p),d(_d) {}
	friend bool operator <(const node &Na,const node &Nb)
	{
		return Na.d < Nb.d;
	}
} u;

struct edge
{
	int to,nxt,wgt;
} info[MAXM];

int D,P,C,F,S,e,ui,vi,wi,ans;
int head[MAXN],dis[MAXN];
priority_queue<node> Q;

inline void addedge(int from,int to,int wgt)
{
	info[++e].to = to;
	info[e].wgt  = wgt;
	info[e].nxt  = head[from];
	head[from]   = e;
}

void dijkstra()
{
	Q.push(node(0,0));
	dis[0] = 0;
	while (!Q.empty())
	{
		u = Q.top();
		Q.pop();
		if (u.d != dis[u.p])
		{
			if (u.d > dis[u.p])
			{
				printf("-1");
				exit(0);
			}
			else continue;
            //判正环。本题中因为优先队列是大根堆,又是尽量让距离更大,
            //负边和负环应该不会有问题。
            //如果有正环的话,当遍历到已经遍历过的点时,答案应该会更大,
            //由此判断是否有正环。
		}
		for (int i = head[u.p]; i; i = info[i].nxt)
		{
			int v = info[i].to;
			if (dis[v] < dis[u.p] + info[i].wgt)
			{
				dis[v] = dis[u.p] + info[i].wgt;
				Q.push(node(v,dis[v]));
			}
		}
	}
}

void init()
{
	freopen("in.txt","r",stdin);
	scanf("%d%d%d%d%d",&D,&P,&C,&F,&S);
	addedge(0,S,D);
	for (int i = 1; i <= P; ++i)
	{
		scanf("%d%d",&ui,&vi);
		addedge(ui,vi,D);
	}
	for (int i = 1; i <= F; ++i)
	{
		scanf("%d%d%d",&ui,&vi,&wi);
		addedge(ui,vi,-wi + D);
	}
	memset(dis,0x8f,sizeof(dis));
}

void work()
{
	dijkstra();
	for (int i = 1; i <= C; ++i)
	{
		ans = max(ans,dis[i]);
	}
	printf("%d",ans);
}

int main()
{
	init();
	work();
	return 0;
}
不知道对不对,反正交上去是A了qwqqwq

回复

17 条回复,欢迎继续交流。

正在加载回复...