1.选择最佳路线
这题就是问多个起点到一个终点的最短路
1.可以直接建反向边，然后从终点跑一遍最短路，最后求一下每个起点的最短路即可
2.建虚拟原点来跑最短路，适用范围广，可以用在多个起点和多个终点的情况，建虚拟原点就是从0号点跟起点连一条边权为0的边，然后跑一遍最短路，因为这时从0号点到终点的最短路相当于从任何一个起点到终点的最短路了，答案就是dist【终点】
#include<bits/stdc++.h> using namespace std; const int N=1010,M=21010; int h[N],e[M],ne[M],w[M],idx; int n,m,T; int dist[N],q[N]; bool st[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int spfa()//spfa算法求最短路 { memset(dist,0x3f,sizeof dist); int hh=0,tt=1; dist[0]=0; q[0]=0; while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0; st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } if(dist[T]==0x3f3f3f3f) return -1; return dist[T]; } int main() { while(~scanf("%d%d%d",&n,&m,&T)) { memset(h,-1,sizeof h); idx=0; int a,b,c,s; while(m--) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } scanf("%d",&s); while(s--) { scanf("%d",&a); add(0,a,0);//建立虚拟原点0，连一条边权为0的边 } printf("%d\n",spfa()); } return 0; }
2.拯救大兵瑞恩
题意就是从左上角到右下角的最短距离，但是跟走迷宫不太一样，他有门的限制，所以要先开门得拿到相应的钥匙才行，走一步的消耗是1点体力
我们可以采用状态分析的方式进行考虑，d[x,y,state]所有从起点走到（x,y）这个格子且拥有的钥匙的状态是state的所有路线的集合
但是由于这里可能会有环 没有拓扑序 实际不能用dp做 只能转换为最短路
把两种转移方式看成两种边
因为这里只有0和1的边所以可以用双端队列广搜来做，然后答案就是d[n,m,0~2^p-1]
然后我们可以用一维的坐标边数两维的位置
#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> pii; const int N=11,M=N*N,E=400,P=1<<10; int h[M],e[E],ne[E],w[E],idx;//w记录的是门需要的钥匙 int n,m,p,k; int g[N][N],key[M]; int dist[M][P]; bool st[M][P]; set<pii> edges;//用来记录出现过的边 void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void built() { int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int u=0;u<4;u++)//枚举四个方向 { int x=i+dx[u],y=j+dy[u]; if(x<=0||x>n||y<=0||y>m) continue;//越界 int a=g[i][j],b=g[x][y]; if(edges.count({a,b})==0) add(a,b,0);//假如不是门或者墙，则说明不用钥匙也能过去，即0就是不需要钥匙 } } int bfs()//双端队列广搜 { memset(dist,0x3f,sizeof dist); dist[1][0]=0;//从起点走，钥匙的状态是0 deque<pii> q; q.push_back({1,0}); while(q.size()) { pii t=q.front(); q.pop_front(); if(st[t.x][t.y]) continue; st[t.x][t.y]=true; if(t.x==n*m) return dist[t.x][t.y];//假如走到了终点直接返回 if(key[t.x])//假如这个位置有钥匙 { int state=t.y|key[t.x];//把这个钥匙的状态加上 if(dist[t.x][state]>dist[t.x][t.y]) { dist[t.x][state]=dist[t.x][t.y];//更新最短距离 q.push_front({t.x,state});//因为边权是0，则加到队头中去 } } for(int i=h[t.x];~i;i=ne[i])//枚举领边 { int j=e[i]; if(w[i]&&!(t.y>>w[i]-1&1)) continue;//假如这个位置有钥匙但是开不了门 if(dist[j][t.y]>dist[t.x][t.y]+1)//更新最短距离 { dist[j][t.y]=dist[t.x][t.y]+1; q.push_back({j,t.y});//因为边权是1则加到队尾 } } } return -1;//反之无解 } int main() { scanf("%d%d%d%d",&n,&m,&p,&k); for(int i=1,t=1;i<=n;i++)//将二维坐标映射到一维的点中 for(int j=1;j<=m;j++) g[i][j]=t++; memset(h,-1,sizeof h); while(k--) { int x1,y1,x2,y2,c; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c); int a=g[x1][y1],b=g[x2][y2]; edges.insert({a,b}),edges.insert({b,a});//标记这两条边有门或者墙 if(c) add(a,b,c),add(b,a,c);//加入是门，则这条边加上这个门需要的钥匙 } built();//建立其他点之间的边权 int s; scanf("%d",&s); while(s--)//读入钥匙 { int x,y,id; scanf("%d%d%d",&x,&y,&id); key[g[x][y]]|=1<<id-1;//将这个位置的钥匙的状态存下来 } printf("%d\n",bfs()); return 0; }
3.最短路计数
按照DP的做法来求方案数，但是满足DP的前提是有拓扑序才能做，最短路但是不满足，所以得按照下面算法来求
天生带有拓扑序的最短路的算法有：dijska和bfs，因为他们处理的时候就是按照最小进行操作，不带有环，所以不会在后面在回过来更新前面的数，所以就拥有拓扑序
所以这题可以直接用dijska来做即可，本身就具备拓扑序
#include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=4e5+10,mod=100003; int h[N],e[M],ne[M],idx; int q[N]; int n,m; int dist[N],cnt[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void bfs() { memset(dist,0x3f,sizeof dist); dist[1]=0; int hh=0,tt=0; q[0]=1; cnt[1]=1;//1到1的方案数是1 while(hh<=tt) { int t=q[hh++]; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+1)//假如能更新最小值 { dist[j]=dist[t]+1; cnt[j]=cnt[t];//把方案数等于能更新我的方案数 q[++tt]=j; } else if(dist[j]==dist[t]+1) cnt[j]=(cnt[j]+cnt[t])%mod;//假如相等，则方案数相加 } } } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); int a,b; while(m--) { scanf("%d%d",&a,&b); add(a,b),add(b,a); } bfs();//跑一遍BFS for(int i=1;i<=n;i++) printf("%d\n",cnt[i]%mod); return 0; }
4.观光
这题较上题需要多求一个次短路径跟次短路径的条数，做法跟上一题一样
#include<bits/stdc++.h> using namespace std; const int N=1e3+10,M=1e4+10; int n,m; int S,T; int h[N],e[M],ne[M],w[M],idx; int dist[N][2],cnt[N][2]; bool st[N][2]; struct Vers//自定义点，因为是大根堆所以重载大于号 { int ver,type,dist; bool operator >(const Vers &W)const { return dist>W.dist; } }; void add(int a,int b,int c) { w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int dijska() { //清空上一层状态 memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); memset(dist,0x3f,sizeof dist); priority_queue<Vers,vector<Vers>,greater<Vers>> heap;//定义一个小根堆 heap.push({S,0,0});//把起点存下来 dist[S][0]=0,cnt[S][0]=1; while(heap.size()) { Vers t=heap.top(); heap.pop(); int ver=t.ver,distance=t.dist,type=t.type,count=cnt[ver][type]; if(st[ver][type]) continue;//假如已经遍历过 st[ver][type]=true; for(int i=h[ver];~i;i=ne[i]) { int j=e[i]; if(dist[j][0]>distance+w[i])//假如可以更新最短路 { dist[j][1]=dist[j][0],cnt[j][1]=cnt[j][0];//则次短路就是最短路，方案数也跟着更新 heap.push({j,1,dist[j][0]}); dist[j][0]=distance+w[i],cnt[j][0]=count;//更新一下最短路和方案数 heap.push({j,0,dist[j][0]}); } else if(dist[j][0]==distance+w[i]) cnt[j][0]+=count;//假如刚好相等，则直接加上方案数 else if(dist[j][1]>distance+w[i])//假如可以更新次短路 { dist[j][1]=distance+w[i],cnt[j][1]=count;//更新一下次短路和方案数 heap.push({j,1,dist[j][1]}); } else if(dist[j][1]==distance+w[i]) cnt[j][1]+=count;//假如刚好相等，则直接加上方案数 } } int res=cnt[T][0]; if(dist[T][0]+1==dist[T][1]) res+=cnt[T][1];//假如次短路等于最短路+1，则加上这个方案数 return res; } int main() { int t; scanf("%d",&t); while(t--) { //清空 memset(h,-1,sizeof h); idx=0; scanf("%d%d",&n,&m); int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } scanf("%d%d",&S,&T); printf("%d\n",dijska()); } return 0; }
