敦爷讲图论的时候讲到了,所以来补一补
POJ-1201
条件不难找:
0<=dis[i]-dis[i-1]<=1
dis[b[i]]-dis[a[i]-1]>=c[i]
但是直接最短路跑出的是最大解,然而题目需要的是最小解,所以要取负跑最短路,或者跑最长路,不过在两种情况下要注意优先队列的排列顺序是正好相反的,不然有可能被t掉
最短路取负
此时要将队列从大到小排
#include<iostream>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#include<bitset>
#include<iterator>
#define bug cout<<"-----------"<<endl;
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=1e9+7;
const ull base=13331;
const double Pi=acos(-1.0);
const ll C=299792458;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int a[N],b[N],c[N];
int head[N],ver[N*2],edge[N*2],Next[N*2],tot=0;
void add(int x,int y,int w){
ver[++tot]=y,edge[tot]=w;
Next[tot]=head[x],head[x]=tot;
}
struct node{
int x,d;
friend bool operator<(node m,node n){
return m.d<n.d;
}
};
int v[N],dis[N];
void spfa(int p){
memset(dis,0x3f,sizeof(dis));
priority_queue<node> Q;
Q.push({p,0});
dis[p]=0;
v[p]=1;
while(!Q.empty()){
int x=Q.top().x;
Q.pop();
v[x]=0;
for(int i=head[x];i;i=Next[i]){
int y=ver[i],w=edge[i];
if(dis[y]>dis[x]+w){
dis[y]=dis[x]+w;
if(v[y]==0){
Q.push({y,dis[y]});
v[y]=1;
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
int maxx=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
a[i]++,b[i]++;
maxx=max(maxx,a[i]-1);
maxx=max(maxx,b[i]);
}
for(int i=1;i<=n;i++){
add(a[i]-1,b[i],-c[i]);
}
for(int i=1;i<=maxx;i++){
add(i,i-1,1);
add(i-1,i,0);
}
spfa(0);
cout<<-dis[maxx]<<endl;
}
//最短路直接跑只能算出最大解
//本题算最小解需要对差分值取负
//0<=-(dis[i]-dis[i-1])<=1
//-1<=dis[i]-dis[i-1]<=0
//dis[i]<=dis[i-1]
//dis[i-1]<=dis[i]+1
//-(dis[b[i]]-dis[a[i]-1])>=c[i]
//dis[b[i]]-dis[a[i]-1]<=-c[i]
//dis[a[i]-1]-c[i]>=dis[b[i]]
最长路
此时要将队列从小到大排
#include<iostream>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#include<bitset>
#include<iterator>
#define bug cout<<"-----------"<<endl;
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=1e9+7;
const ull base=13331;
const double Pi=acos(-1.0);
const ll C=299792458;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int a[N],b[N],c[N];
int head[N],ver[N*2],edge[N*2],Next[N*2],tot=0;
void add(int x,int y,int w){
ver[++tot]=y,edge[tot]=w;
Next[tot]=head[x],head[x]=tot;
}
struct node{
int x,d;
friend bool operator<(node m,node n){
return m.d>n.d;
}
};
int v[N],dis[N];
void spfa(int p){
memset(dis,-0x3f,sizeof(dis));
priority_queue<node> Q;
Q.push({p,0});
dis[p]=0;
v[p]=1;
while(!Q.empty()){
int x=Q.top().x;
Q.pop();
v[x]=0;
for(int i=head[x];i;i=Next[i]){
int y=ver[i],w=edge[i];
if(dis[y]<dis[x]+w){
dis[y]=dis[x]+w;
if(v[y]==0){
Q.push({y,dis[y]});
v[y]=1;
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
int maxx=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
a[i]++,b[i]++;
maxx=max(maxx,a[i]-1);
maxx=max(maxx,b[i]);
}
for(int i=1;i<=n;i++){
add(a[i]-1,b[i],c[i]);
}
for(int i=1;i<=maxx;i++){
add(i,i-1,-1);
add(i-1,i,0);
}
spfa(0);
cout<<dis[maxx]<<endl;
}