|
昨天一天才把DJ&SPFA卷明白，麻了麻了
2021年暑训最短路专题
Problem A：
Til the Cows Come Home
题目大意：已知一个有T条边，N个点的无向图，求从点1到点N的最短路（板子题）
题解：数据量不大，DJ可以不需要优化，当点的数据超过1e4时最好采用堆优化DJ。
AC代码：（堆优化DJ）
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2e3+7;
const int inf=0x3f3f3f3f;
struct edge{
int to,cost;
};
vector<edge> G[maxn];
int d[maxn];
int n,t;
priority_queue<P,vector<P>,greater<P> > que;
void dij(int s){
fill(d+1,d+1+n,inf);
d[s]=0;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();
que.pop();
int v=p.second;
if(d[v]<p.first)continue;
for(int i=0;i<G[v].size();i++){
edge e=G[v][i];
if(d[e.to]>d[v]+e.cost) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}
int main(){
cin>>t>>n;
for(int i=1;i<=t;i++){
int a,b,c;
cin>>a>>b>>c;
edge e;
e.to=b,e.cost=c;
G[a].push_back(e);
e.to=a;
G[b].push_back(e);
}
dij(1);
cout<<d[n];
return 0;
}
Problem B：
Frogger
题目大意：青蛙A在第一块石头，青蛙B在第二块石头，旁边还有其他石头，给出每块石头的坐标，青蛙A有很多种方案到达第二块石头，它想知道所有路径中最大的最短距离。
题解：（堆优化DJ）这道题难在无法理解如何松弛，在求最短路的时候，d[x]数组保存的是从源点到达点x路径中最大的最短距离，由于是求最短距离，
我们的堆要是小顶堆，这样才能保证每次取出的路径是最短的，在此基础上对每个端点进行松弛（d[i]=min(d[i],max(d[v],e.cost)))，尽量让最短的边达到最大。
AC代码：
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;
typedef pair<int,double> P;
const int maxn=1e3+7;
const int inf=0x3f3f3f3f;
struct edge{
int to;
double cost;
};
vector<edge>G[maxn];
int n;
double x[202],y[202];
double d[maxn];
void dij(int s){
fill(d+1,d+1+n,inf);
d[s]=0;
priority_queue<P,vector<P>,greater<P> >que;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();
que.pop();
int v=p.second;
if(d[v]<p.first)continue;
for(int i=0;i<G[v].size();i++){
edge e=G[v][i];
if(d[e.to]>max(d[v],e.cost)){
d[e.to]=max(d[v],e.cost);
que.push(P(d[e.to],e.to));
}
}
}
}
int main(){
int cnt=1;
while(cin>>n&&n){
for(int i=1;i<=202;i++)G[i].clear();
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
double dis=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
edge e;
e.to=j;
e.cost=dis;
G[i].push_back(e);
}
}
dij(1);
cout<<"Scenario #"<<cnt++<<endl<<"Frog Distance = ";
cout<<fixed<<setprecision(3)<<d[2]<<endl<<endl;
}
}
Problem C:
Heavy Transportation
题目大意：与B类似，求所有路径中最小的最大值。
题解：与B类似，d[x]数组初始化为0，d[s]初始化为inf，优先队列选用大根堆，松弛方程为d[e.to]=max(d[e.to],min(d[v],e.cost));
AC代码：
#include<iostream>
#include<vector>
#include<queue>
#include<stdio.h>
using namespace std;
const int maxn=1e3+7;
const int inf=0x3f3f3f3f;
typedef pair<int,int>P;
int t,n,m;
struct edge {
int to,cost;
};
vector<edge> G[maxn];
int d[maxn];
void dj(int s){
fill(d+1,d+1+n,0);
d[s]=inf;
priority_queue<P,vector<P>,less<P> >que;
que.push(P(inf,s));
while(!que.empty()){
P p=que.top();
que.pop();
int v=p.second;
if(d[v]<p.first)continue;
for(int i=0;i<G[v].size();i++){
edge e=G[v][i];
if(d[e.to]<min(d[v],e.cost)){
d[e.to]=min(d[v],e.cost);
que.push(P(d[e.to],e.to));
}
}
}
}
int main(){
scanf("%d",&t);
int cnt=1;
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge e;
e.to=a,e.cost=c;
G[b].push_back(e);
e.to=b;
G[a].push_back(e);
}
dj(1);
printf("Scenario #%d:\n%d\n\n",cnt++,d[n]);
for(int i=1;i<=n;i++)G[i].clear();
}
return 0;
}
Problem D:
Silver Cow Party
题目大意：N个农场，M条路（单向边），其中编号为X的农场要举行party，求其他农场的cow们中往返时间最长的那只的往返时间。
题解：自己画张图很容易证明a到b的最短路，可以由b到a所求最短路的矩阵的转置所求出。所以本题两次Dj即可完成。
AC代码：
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int>P;
const int maxn=1e3+7;
const int inf=0x3f3f3f3f;
struct edge{
int to,cost;
};
vector<edge>G1[maxn],G2[maxn];
int n,m,x,d1[maxn],d2[maxn];
void dj1(int s){
fill(d1+1,d1+1+n,inf);
d1[s]=0;
priority_queue<P,vector<P>,greater<P> >que;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();
que.pop();
int v=p.second;
if(d1[v]<p.first)continue;
for(int i=0;i<G1[v].size();i++){
edge e=G1[v][i];
if(d1[e.to]>d1[v]+e.cost){
d1[e.to]=d1[v]+e.cost;
que.push(P(d1[e.to],e.to));
}
}
}
}
void dj2(int s){
fill(d2+1,d2+1+n,inf);
d2[s]=0;
priority_queue<P,vector<P>,greater<P> >que;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();
que.pop();
int v=p.second;
if(d2[v]<p.first)continue;
for(int i=0;i<G2[v].size();i++){
edge e=G2[v][i];
if(d2[e.to]>d2[v]+e.cost){
d2[e.to]=d2[v]+e.cost;
que.push(P(d2[e.to],e.to));
}
}
}
}
int main(){
cin>>n>>m>>x;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
edge e;
e.to=b,e.cost=c;
G1[a].push_back(e);
e.to=a;
G2[b].push_back(e);
}
dj1(x);
dj2(x);
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,d1[i]+d2[i]);
}
cout<<ans;
}
Problem E
Currency Exchange
题目大意：已知你是Nike，你家附近有M台货币转换机，可以转换N种货币，你目前有S种类的货币V枚，每台货币转换机具有六个数据：a，b为两种货币的类型，Cab、Rab是a转化为b的汇率及佣金，Cba、Rba是b转化为a的汇率及佣金。
a转化为b的转化公式：设a有k枚，那么可以转化（k-Rab）*Cab枚b。
问：是否有可能在转化（不限次数）后，使自己本金变多？
题解：由于需要增加本金，那么我们需要在这些转换规则中找到一个正环，
利用SPFA解决问题。
AC代码：
#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<math.h>
#include<stack>
#include<map>
#include<limits.h>
#include<vector>
#include<string.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 1e7;
const int M = 1e5+7;
#define INF 1e7+5
#define INM INT_MIN
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define dbg(x) cout << "now this num is " << x << endl;
#define sd(a) scanf("%d",&a)
#define sld(a) scanf("%lld",&a)
#define sdd(a,b) scanf("%d %d",&a,&b)
#define sddd(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pr(a) printf("%d\n",a)
#define plr(a) printf("%lld\n",a)
#define pr_(a) printf("%d ",a)
#define _pr(a) printf(" %d",a)
int vis[105],n,m,s;
double dis[105],v;
struct Node
{
int to;
double a1,b1;
};
vector<Node> G[105];
bool spfa(int x)
{
memset(vis,0,sizeof(vis));
vis[x] = 1;
for(int i=1;i<=n;++i) dis[i] = 0;
dis[x] = v;
queue<int> Q;
Q.push(x);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = 0;
for(int i=0;i<G[u].size();++i)
{
Node e = G[u][i];
if(dis[e.to] < (dis[u]-e.b1)*e.a1)
{
dis[e.to] = (dis[u]-e.b1)*e.a1;
if(!vis[e.to])
{
vis[e.to] = 1;
Q.push(e.to);
}
}
if(dis[x] > v) return true;
}
}
return false;
}
int main()
{
sddd(n,m,s);
scanf("%lf",&v);
while(m--)
{
int a,b;
double a1,b1,a2,b2;
sdd(a,b);
scanf("%lf %lf %lf %lf",&a1,&b1,&a2,&b2);
Node p,q;
p.to = b;p.a1 = a1;p.b1 = b1;
q.to = a;q.a1 = a2;q.b1 = b2;
G[a].pb(p);
G[b].pb(q);
}
if(spfa(s)) printf("YES\n");
else printf("NO\n");
}
Problem F:
Wormholes
题目大意：一个农夫有N块田，M条路（双向），每条路需要花费一定时间，他的田中还存在W个虫洞，这些虫洞可以将农夫传送回一定时间以前（单向），问：有没有一种方案能使他回到初始点与自己碰面。
题解：虫洞的时间为负，SPFA判断是否存在负环即可。
AC代码：
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int>P;
const int maxn=5e2+7;
const int inf=0x3f3f3f3f;
int d[maxn];
int n,m,w;
int vis[maxn];
struct edge{
int to,cost;
};
vector<edge>G[maxn];
bool SPFA(int s){
int cnt[maxn]={0};
fill(d+1,d+1+n,inf);
fill(vis+1,vis+1+n,0);
d[s]=0;
vis[s]=1;
queue<P>que;
que.push(P(s,cnt[s]));
while(!que.empty()){
P p=que.front();
que.pop();
int v=p.first;
vis[v]=0;
for(int i=0;i<G[v].size();i++){
edge e=G[v][i];
if(d[e.to]>d[v]+e.cost){
d[e.to]=d[v]+e.cost;
if(!vis[e.to]){
que.push(P(e.to,++cnt[e.to]));
vis[e.to]=1;
}
}
}
for(int i=1;i<=n;i++){
if(cnt[i]>n)return 0;
}
}
return 1;
}
int main(){
int t;
cin>>t;
while(t--){
for(int i=1;i<=maxn;i++)G[i].clear();
cin>>n>>m>>w;
for(int i=1;i<=m;i++){
int a,b,c;
edge e;
cin>>a>>b>>c;
e.to=b,e.cost=c;
G[a].push_back(e);
e.to=a;
G[b].push_back(e);
}
for(int i=1;i<=w;i++){
int a,b,c;
edge e;
cin>>a>>b>>c;
e.to=b,e.cost=-c;
G[a].push_back(e);
}
if(SPFA(1)){
cout<<"NO"<<endl;
}
else cout<<"YES"<<endl;
}
return 0;
}
待补全
|