3305 作物杂交
用另外一个数组存杂交结果，初始结点都为0，遍历所有杂交结果，只要可以减小就加入到队列中。
if条件是距离小于两个max，因为必须要保证其父辈已经产生。
另外注意使用普通队列即可；
和dijkstra中的st数组不同，这里只用来判断是否是在q中。
所以所有的初始结点都要st为1，pop的时候将结点st置为0.
#include<bits/stdc++.h>
using namespace std;
//3305作物杂交
const int N=2010, M=2e5+10;
int e[M],ne[M],h[N],target[M],dis[N],timee[N],idx,st[N];
int n,m,k,t;
queue<int>q;
void add(int x,int y,int c)
{
e[idx]=y;
ne[idx]=h[x];
target[idx]=c;
h[x]=idx++;
}
void spfa()
{
while(q.size())
{
int t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i!=-1;i=ne[i])
{
int u=target[i];
if(dis[u]>max(dis[t],dis[e[i]])+max(timee[t],timee[e[i]]))
{
dis[u]=max(dis[t],dis[e[i]])+max(timee[t],timee[e[i]]);
if(st[u])continue;
else
{
q.push(u);
st[u]=1;
}
}
}
}
}
int main()
{
cin>>n>>m>>k>>t;
memset(h,-1,sizeof(h));
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++)//种植时间
{
cin>>timee[i];
}
for(int i=0;i<m;i++)//初始节点
{
int x;
cin>>x;
dis[x]=0;
q.push(x);
st[x]=1;
}
while(k--)
{
int x,y,tt;
cin>>x>>y>>tt;
add(x,y,tt);
add(y,x,tt);
}
spfa();
cout<<dis[t]<<endl;
}
851 spfa求最短路
板子还是老出错。
要记得st数组和dis数组的更新；入队时、出队时候、更新时候；
把st的判断和dis的判断搞反了，先看是否可以更新，可更新一定要先更新。
不要看到st在队列中就不更新了。
#include<bits/stdc++.h>
using namespace std;
//851 spfa求最短路
const int N=1e5+10;
int e[N],ne[N],h[N],w[N],idx,dis[N],st[N];
int n,m;
void add(int x,int y,int c)
{
e[idx]=y;
ne[idx]=h[x];
w[idx]=c;
h[x]=idx++;
}
void spfa()
{
queue<int>q;
q.push(1);
dis[1]=0;
st[1]=1;
while(q.size())
{
int t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i!=-1;i=ne[i])
{
int u=e[i];//结点是谁
int dist=w[i];//边长是
//只要这个边可更新就更新不要管是否有st
if(dis[u]>dis[t]+dist)//没在队列里
{
dis[u]=dis[t]+dist;
if(!st[u])
{
q.push(u);
st[u]=1;
}
}
}
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof(dis));
memset(dis,0x3f,sizeof(dis));
while(m--)
{
int x,y,c;
cin>>x>>y>>c;
add(x,y,c);
}
spfa();
if(dis[n]==1061109567)cout<<"impossible"<<endl;
else{
cout<<dis[n]<<endl;
}
}
852 spfa判断环路
所有结点要先入队；
因为存在一种情况就是不连通。
所以要把所有的节点入队;dis的数值随意。
所以最短路的求法和负环的判断是不可统一的。
#include<bits/stdc++.h>
using namespace std;
// 852. spfa判断负环
const int N=1e5+10;
int e[N],ne[N],h[N],w[N],idx,dis[N],st[N],cnt[N];
int n,m;
void add(int x,int y,int c)
{
e[idx]=y;
ne[idx]=h[x];
w[idx]=c;
h[x]=idx++;
}
int spfa()
{
queue<int>q;
for(int i=1;i<=n;i++)q.push(i),st[i]=1;
while(q.size())
{
int t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i!=-1;i=ne[i])
{
int u=e[i];//结点是谁
int dist=w[i];//边长是
//只要这个边可更新就更新不要管是否有st
if(dis[u]>dis[t]+dist)//没在队列里
{
dis[u]=dis[t]+dist;
cnt[u]=cnt[t]+1;
if(cnt[u]>=n)return 1;
if(!st[u])
{
q.push(u);
st[u]=1;
}
}
}
}
return 0;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof(dis));
//memset(dis,0x3f,sizeof(dis));
while(m--)
{
int x,y,c;
cin>>x>>y>>c;
add(x,y,c);
}
if(spfa())cout<<"Yes"<<endl;
else{
cout<<"No"<<endl;
}
}
341 最优贸易
我们要找到两个城市在一个城市里买，另一个城市里卖掉；
y的思路：以某个点为界，求其左边买入的水晶球的最低价格，求其右边卖出的水晶球的最高价格；然后遍历相减；
之前都是在最短路上求sum属性，现在要求min属性。要求i左边的就从0开始走。i右边的就从n开始走，所以要保存两个相反的h数组。
又要保持路是可达的。
有bug不要盲目找错动动脑筋。
#include<bits/stdc++.h>
using namespace std;
// 341 最优贸易
const int N=1e5+10,M=5e5+10;
int e[M],ne[M],rh[N],h[N],w[N],idx,minn[N],stt[N],st[N],maxx[N];
//minn和maxx都是截止到i这个点（而且路可通）的最大最小值。
int n,m;
//笑死开始忘了怎么调用函数了，int h[]即可
void add(int h[],int x,int y)
{
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
void spfa(int flag)
{
//用两个数组，minn和maxx 两个队列
//spfa分别从正着和逆着两条路找截止到某个点的最大值和最小值。
minn[1]=w[1];
queue<int>q;
st[1]=1;
q.push(1);
maxx[n]=w[n];
queue<int>qq;
stt[n]=1;
qq.push(n);
if(flag)
{
while(q.size())
{
int t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i!=-1;i=ne[i])
{
int u=e[i];
if(minn[u]>min(minn[t],w[u]))
{
minn[u]=min(minn[t],w[u]);//先更新
//这个位置一定要注意只要符合条件就更新，只有没有在数组中的才加入数组
if(!st[u])
{
q.push(u);
st[u]=1;
}
}
}
}
}
else
{
while(qq.size())
{
int t=qq.front();
qq.pop();
stt[t]=0;
for(int i=rh[t];i!=-1;i=ne[i])
{
int u=e[i];
if(maxx[u]<max(maxx[t],w[u]))
{
maxx[u]=max(maxx[t],w[u]);
if(!stt[u])
{
qq.push(u);//只有没有在队列中的时候才向里面放
stt[u]=1;
}
}
}
}
}
}
int main()
{
memset(minn,0x3f,sizeof(minn));
memset(maxx,-0x3f,sizeof(maxx));
cin>>n>>m;
memset(h,-1,sizeof(h));
memset(rh,-1,sizeof(rh));
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
while(m--)
{
int x,y,c;
cin>>x>>y>>c;
add(h,x,y);
add(rh,y,x);
if(c==2)
{
add(h,y,x);
add(rh,x,y);
}
}
spfa(1);
spfa(0);
int res=0;
//遍历求取以某个点为分界点求最大差值
for(int i=1;i<=n;i++)
{
res=max(maxx[i]-minn[i],res);
// cout<<maxx[i]<<" "<<minn[i]<<endl;
}
cout<<res<<endl;
}
