P2136 拉近距离

Posted Thu Nov 28 2019. 635 words. 3 min read.

This article was last updated on days ago, the information described in the article may be outdated.

思路

我是源点,你是终点。我们之间有负权环。 ——小明

负环的 经验题 and 语文阅读理解?

此题中的 w 为减少的距离,与正常的不同。

结合输入输出

输入样例
3 3
1 2 3
2 3 -1
3 1 -10
输出
-2

再画两张图

这时你就会发现只需将 -w 当作权值进行最短路运算即可

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 5010
#define MAXM 50010
const int INF = 1e9;
using namespace std;

int n,m,u,v,w,cnt,T;
int head[MAXN],dis[MAXN],vis[MAXN],num[MAXN];
struct Edge {
int to,next,w;
}edge[MAXM<<1];
queue <int> q;

void spfa() {
fill(dis+1,dis+n+1,INF);
q.push(1);
vis[1] = 1;
dis[1] = 0;

while(!q.empty()) {

int u = q.front();
q.pop();
vis[u] = 0;
for(int i=head[u];i;i=edge[i].next) {
int v = edge[i].to;
if(dis[v]>dis[u]+edge[i].w) {
dis[v] = dis[u] + edge[i].w;
if(!vis[v]) {
q.push(v);
vis[v] = 1;
num[v]++;
if(num[v]>n) {
cout << "Forever love";
return;
}
}
}
}
}
cout << dis[n];
}

void add(int u,int v,int w) {
edge[++cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}

int main() {
cin >> n >> m;
for(int i=1;i<=m;i++) {
cin >> u >> v >> w;
add(u,v,-w);
}
spfa();
return 0;
}

然后你就 wa 一个点。
让我们再认真看看题目,只能小明主动吗?小红也可以主动点啊,所以再从 n 开始跑一次就可以 ac 了

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 5010
#define MAXM 50010
const int INF = 1e9;
using namespace std;

int n,m,u,v,w,cnt,T;
int head[MAXN],dis[MAXN],vis[MAXN],num[MAXN];
struct Edge {
int to,next,w;
}edge[MAXM<<1];
queue <int> q;

bool spfa(int s) {
fill(dis+1,dis+n+1,INF);
memset(vis,0,sizeof(vis));

q.push(s);
vis[s] = 1;
dis[s] = 0;

while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for(int i=head[u];i;i=edge[i].next) {
int v = edge[i].to;
if(dis[v]>dis[u]+edge[i].w) {
dis[v] = dis[u] + edge[i].w;
if(!vis[v]) {
q.push(v);
vis[v] = 1;
num[v]++;
if(num[v]>n) {
cout << "Forever love";
exit(0);
}
}
}
}
}
return 0;
}

void add(int u,int v,int w) {
edge[++cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}

int main() {
cin >> n >> m;
for(int i=1;i<=m;i++) {
cin >> u >> v >> w;
add(u,v,-w);
}
spfa(1);
int mi=dis[n];
spfa(n);
cout<<min(mi,dis[1]);
return 0;
}

至此绿题++

模板传送门


Comments

Unable to load Disqus, please make sure your network can access.