社区讨论
可以用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了
回复
共 17 条回复,欢迎继续交流。
正在加载回复...