最短路复习
租用游艇
典型的Dijkstra，套套模板
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200+5;
const int INF=0x7fffffff;
const int inf=1000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
int eg[MAX_N][MAX_N];
int d[MAX_N];
int used[MAX_N];
int main()
{
int n;
scanf("%d",&n);
int i;
for(i=1; i<n; i++)
{
int j;
for(j=i+1; j<=n; j++)
{
scanf("%d",&eg[i][j]);
eg[j][i]=inf;
}
}
fill(d,d+MAX_N,inf);
d[1]=0;
while(1)
{
int v=-1;
for(i=1; i<=n; i++)
{
if(used[i]==0&&(v==-1||d[i]<d[v]))
{
v=i;
}
}
if(v==-1)
break;
used[v]=1;
for(i=1; i<=n; i++)
{
if(i==v)
continue;
if(eg[v][i]+d[v]<d[i])
{
d[i]=d[v]+eg[v][i];
}
}
}
cout<<d[n]<<endl;
}
ob Hunt S
要赚更多的钱，可以换个思路，把赚的钱取相反数，用出去的钱当正数，作为边的权值，那么求出最短路的值，最后取相反数即可。这题理论上是存在负环的，所以必然要用Bellman-Ford或者SPFA（优化）
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=400+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
int eg[MAX_N][MAX_N];
int d[MAX_N];
int main()
{
int money,m1,n,m2,x;
cin>>money>>m1>>n>>m2>>x;
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
eg[i][j]=inf;
}
fill(d,d+1+n,inf);
for(i=1;i<=m1;i++)
{
int l,r;
scanf("%d%d",&l,&r);
eg[l][r]=-money;
}
for(i=1;i<=m2;i++)
{
int l,r,value;
scanf("%d%d%d",&l,&r,&value);
eg[l][r]=value-money;
}
int k;
for(i=1;i<=n;i++)
{
if(i==x)
continue;
d[i]=eg[x][i];
}
d[x]=0;
int flag;
for(i=1;i<=n;i++)
{
flag=0;
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(j==k)
continue;
if(d[k]>d[j]+eg[j][k])
{
//cout<<j<<' '<<k<<endl;
flag=1;
d[k]=d[j]+eg[j][k];
}
}
}
if(!flag)
break;
}
if(flag)
{
cout<<-1<<endl;
}
else
{
int mn=inf;
for(i=1;i<=n;i++)
{
mn=min(mn,d[i]);
}
cout<<-mn+money<<endl;
}
}
最短路计数
这题我是觉得bfs方便些，注意每一格第一次出现的时候推入队列，当发现当前步数和这一格的最小步数相同时，这一格的方案数就是原先方案数加上一个方案数。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=1000000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=100003;
const double pi=4*atan(1.0);
vector<int>v[MAX_N];
int d[MAX_N];
int ans[MAX_N];
int vis[MAX_N];
struct node
{
int id,step;
};
queue<node>q;
int main()
{
int n,m;
cin>>n>>m;
fill(d,d+1+n,inf);
int i;
for(i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
v[l].pb(r);
v[r].pb(l);
}
q.push(node{
1,0});
ans[1]=1;
vis[1]=1;
while(!q.empty())
{
int num=q.front().id;
int step=q.front().step;
q.pop();
for(i=0;i<v[num].size();i++)
{
int e=v[num][i];
if(!vis[e])
{
vis[e]=1;
q.push(node{
e,step+1});
d[e]=step+1;
//q.push(node{e,step+1});
}
if(d[e]==step+1)
{
ans[e]=(ans[e]+ans[num])%mod;
//q.push(node{e,step+1});
}
//cout<<e<<' '<<d[e]<<endl;
}
}
for(i=1;i<=n;i++)
{
cout<<ans[i]<<endl;
}
}
单源最短路径（标准版）
Dijkstra+优先队列优化，我写的有点怪，因为太久没写了，都是自己临时想的，可能跟原先的模板差的有点大。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=1000000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=100003;
const double pi=4*atan(1.0);
struct NODE
{
int to;
int value;
};
vector<NODE>v[MAX_N];
struct node
{
int id;
int d;
bool friend operator<(node a,node b)
{
return a.d>b.d;
}
}a[MAX_N];
priority_queue<node>q;
int cost[MAX_N];
int used[MAX_N];
int main()
{
int n,m,x;
scanf("%d%d%d",&n,&m,&x);
int i;
for(i=1;i<=n;i++)
{
a[i].id=i;
a[i].d=inf;
}
for(i=1;i<=m;i++)
{
int l,r,value;
scanf("%d%d%d",&l,&r,&value);
v[l].pb(NODE{
r,value});
}
a[x].d=0;
q.push(a[x]);
while(!q.empty())
{
node p=q.top();
q.pop();
if(used[p.id])
continue;
used[p.id]=1;
for(i=0;i<v[p.id].size();i++)
{
NODE u=v[p.id][i];
if(p.d+u.value<a[u.to].d)
{
a[u.to].d=p.d+u.value;
q.push(a[u.to]);
}
}
}
for(i=1;i<=n;i++)
{
printf("%d%c",a[i].d,i==n?'\n':' ');
}
}
棋盘
我也不知道为什么我要在最短路的专题里面用dfs，然后就是疯狂超时，给他疯狂剪枝。总之直接dfs肯定超时，就要考虑剪枝，以下可能要剪掉
1.目前用的金币大于已经求得的答案最小值。
2.用一个数组保存到每个点所用金币最小值，如果当前使用金币大于这个点的最小值，那么剪掉。
3.没有颜色的情况，只需要搜索跟上一格颜色相同的情况。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=1000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=100003;
const double pi=4*atan(1.0);
int chess[MAX_N][MAX_N];
int used[MAX_N][MAX_N];
int dir[4][2]= {
{
1,0},{
-1,0},{
0,-1},{
0,1}};
int ans=INF;
int m,n;
int d[MAX_N][MAX_N];
void dfs(int x,int y,int flag,int sum)
{
if(x==m&&y==m)
{
//cout<<sum<<endl;
ans=min(ans,sum);
return;
}
int i;
for(i=0; i<4; i++)
{
int dx=x+dir[i][0];
int dy=y+dir[i][1];
if(dx>=1&&dy>=1&&dx<=m&&dy<=m&&used[dx][dy]==0)
{
if(chess[dx][dy]==chess[x][y])
{
//cout<<dx<<' '<<dy<<endl;
used[dx][dy]=1;
if(sum<ans)
{
if(sum<d[dx][dy])
{
d[dx][dy]=sum;
dfs(dx,dy,0,sum);
}
}
used[dx][dy]=0;
}
else if(chess[dx][dy])
{
used[dx][dy]=1;
if(sum+1<ans)
{
if(sum+1<d[dx][dy])
{
d[dx][dy]=sum+1;
dfs(dx,dy,0,sum+1);
}
}
used[dx][dy]=0;
}
else if(flag==0)
{
used[dx][dy]=1;
chess[dx][dy]=chess[x][y];
if(sum+2<ans)
{
if(sum+2<d[dx][dy])
{
d[dx][dy]=sum+2;
dfs(dx,dy,1,sum+2);
}
}
used[dx][dy]=0;
chess[dx][dy]=0;
}
}
}
}
int main()
{
int i,j;
cin>>m>>n;
for(i=1; i<=n; i++)
{
int x,y,op;
scanf("%d%d%d",&x,&y,&op);
chess[x][y]=++op;
}
for(i=1; i<=m; i++)
for(j=1; j<=m; j++)
d[i][j]=INF;
used[1][1]=1;
dfs(1,1,0,0);
if(ans==INF)
ans=-1;
cout<<ans<<endl;
}
华为工作强度 806人发布
查看45道真题和解析