按题目难度写
1.租用游艇
最明显的最短路 可以直接floyed
由于这次floyed是无相边的 所以我们将其枚举的时候变为单向（利用r(i,j)中i<j）
#include<iostream> #include<algorithm> using namespace std; int dp[210][210]; int main() { int n; cin >> n; for(int i=1;i<=n-1;i ) for (int j = i 1; j <= n; j ) { cin >> dp[i][j]; } for (int i = 1; i < n - 1; i ) { for (int j = i 2; j <= n; j ) { for (int k = i 1; k < j; k ) { dp[i][j] = min(dp[i][j], dp[i][k] dp[k][j]); } } } cout << dp[1][n]<<endl; }2 邮递员送信
我们可以清楚地发现，对于所有点，我们需要它从源点到回到源点 对于前者，我们可以直接一个dij从源点出发就好 对于后面 因为一切都要回到源点 所以我们干脆建立反向，再跑一次dij 答案是两者的结合
#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define int long long int n, m, s, head[10010], cnt; struct sju { int u, v, dis; }a[501000]; struct edge { int to, dis, next; }e[510000]; int ans,dis[5001000], vis[10010]; void add(int u, int v, int dis) { e[ cnt].dis = dis; e[cnt].next = head[u]; e[cnt].to = v; head[u] = cnt; } struct node { int dis, pos; bool operator<(const node&x)const { return x.dis < dis; } }; void dij() { memset(dis, 0x3f, sizeof(dis)); dis[1] = 0; std::priority_queue<node>q; q.push({ 0,1 }); while (!q.empty()) { int x = q.top().pos; q.pop(); if (vis[x]) continue; vis[x] = 1; for (int i = head[x]; i; i = e[i].next) { int y = e[i].to; if (!vis[y]) if (dis[y] > dis[x] e[i].dis) { dis[y] = dis[x] e[i].dis; q.push({ dis[y],y }); } } } for (int i = 1; i <= n; i ) ans = dis[i]; } signed main() { cin >> n >> m; for (int i = 1; i <= m; i ) { int x, y, z; cin >> x >> y >> z; add(x, y, z); a[i].u = x, a[i].v = y, a[i].dis = z; } dij(); memset(head, 0, sizeof(head)); memset(e , 0,sizeof(e)); memset(vis, 0, sizeof(vis)); cnt = 0; for (int i = 1; i <= m; i ) add(a[i].v, a[i].u, a[i].dis); dij(); cout << ans; }3
[USACO09NOV]Job Hunt S
我们可以发现，到达每个城市都会赚钱 这相当于一个点权，那么如何将其与最短路联系起来呢？ 考虑当你到达一个城市时，你会得到它 我们将实现这座城市的路边权赋值D 我们为飞机付费 D 你可以发现，你想赚最多的钱 找到一点:从源点到这一点的最大距离 -一是有正环
改一下spfa就好了：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn = 1e5 5; int head[maxn],ans,cnt, dist[maxn]; int sum[maxn]; bool vis[maxn]; int d, p, c, f, s; struct edge { int to, dis, next; }e[maxn<<1]; void add(int u, int v, int dis) { e[ cnt].dis = dis; e[cnt].next = head[u]; e[cnt].to = v; head[u] = cnt; } bool spfa(int u) { queue<int>q; memset(vis, 0, sizeof(vis)); memset(sum, 0, sizeof(sum)); memset(dist, 0, sizeof(dist)); vis[u] = 1; sum[u] ; q.push(u); dist[u] = d; while (!q.empty()) { int x = q.front(); q.pop(); vis[x] = 0; for (int i = head[x]; i; i = e[i].next) { int y = e[i].to; if (dist[y] < dist[x] e[i].dis) { dist[y] = dist[x] e[i].dis; if (!vis[y]) { if ( sum[y] >= c) return 1; vis[y] = 1; q.push(y); } } } } for (int i = 1; i <= c; i ) ans = max(ans, dist[i]); return 0; } int main() { cin >> d >> p >> c >> f >> s; for (int i = 1; i <= p; i ) { int x, y; cin >> x >> y; add(x, y, d); } for (int i = 1; i <= f; i ) { int x, y, z; cin >> x >> y >> z; add(x, y, d - z); } if (spfa(s)) { cout << -1<<endl; } else { cout << ans; } }四、最短路计数
我们发现这题求得是最短路的条数，也就是方案数 一般和dp关系密不可分 所以考虑dp
我们将所有边权赋值为1 跑一次最短路，同时保持最短路dp[i]变化
情况分为 1：dis[y]<dis[x] 1:代表此时更新最短短路 所以dp[y]=dp[x];
2:dis[y]==dis[x] 1；这意味着它与我们此时发现的最短路相同 所以dp[y] =dp[x];
最后输出dp即可
#include<iostream> #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int mod = 100003; int n, m; struct edge { int to,next; }e[2001000]; struct node { int pos, dis; bool operator<(const node&x)const { return x.dis <dis; } }; int dis[1000100],head[1000100], cnt; bool vis[1000100]; int ans[1000100]; void add(int u, int v) { e[ cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } void dij() { std::priority_queue <node > q; q.push({1，0})； memset(dis, 0x3f3f3f, sizeof(dis)); dis[1] = 0; ans[1] = 1; while (!q.empty()) { int x = q.top().pos; q.pop(); if (vis[x]) continue; vis[x] = 1; for (int i = head[x]; i; i = e[i].next) { int y = e[i].to; if (dis[y] > dis[x] 1) { dis[y] = dis[x] 1;//第次经过时就是最短路
ans[y] = ans[x];
if (!vis[y])
{
q.push({ y,dis[y] });
}
}
else if(dis[y]==dis[x]+1)
{
ans[y]+=ans[x];
ans[y] %= mod;
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
add(u, v);
add(v,u);
}
dij();
for (int i = 1; i <= n; i++)
cout << ans[i] % mod<< endl;
}P3371 P4779 P3385 均为模板题
9 灾后重建：他第一篇讲的很好
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
int n, m, q;
int d[101000];
int a[10010][10010];
void folyed(int k)
{
for (int i = 0; i <n; i++)
for (int j = 0; j <n; j++)
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
signed main()
{
cin >> n >> m;
for (int i = 0; i <n; i++)
cin >> d[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
a[i][j] = 1e9;
for (int i = 1; i <= m; i++)
{
int a1, b, c;
cin >> a1 >> b >> c;
a[a1][b] = c;
a[b][a1] = c;
}
cin >> q;
int now = 0;
for (int i = 1; i <= q; i++)
{
int x, y, z;
cin >> x >> y >> z;
while (d[now] <= z&&now <=n-1)
{
folyed(now);
now++;
}
if (d[x]>z||d[y]>z||a[x][y] == 1e9 || a[y][x] ==1e9)
cout << -1 << endl;
else
cout << a[x][y]<<endl;
}
}10 棋盘：bfs
假设无颜色为-1 有颜色为1/0
注意要点在于
我们如何处理变色后无法连续使用魔法：无法使用魔法的情况当且仅当我们此时本身color为-1 下一位也是-1 此时两者是不连通的 所以记录每次走到的变成的颜色和真实的颜色就好
这题我之前写的 就bfs 直接暴力跑 虽然可以加优先队列优化 主要是我这个没有标记vis 不管有剪纸
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
int n, m;
struct node
{
int x, y, cost, color;
};
int dx[5] = { 0,0,0,1,-1 };
int dy[5] = { 0,1,-1,0,0 };
int map[110][110];
int val[110][110];//记录走到x，y的最短花费
signed main()
{
cin >> n >> m;
memset(map, -1, sizeof(map));
memset(val, 0x3f3f3f, sizeof(val));
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
map[x][y] = z;
}
int ans = 1e9;
val[1][1] = 0;
queue<node>q;
q.push({ 1, 1, val[1][1], map[1][1] });
while (!q.empty())
{
node tmp = q.front();
if (q.front().cost > ans)
{
q.pop();
continue;
}
else
{
if (tmp.y == n && tmp.x == n)
{
ans = min(ans, tmp.cost);
q.pop();
continue;
}
else
{
q.pop();
for (int i = 1; i <= 4; i++)
{
int dx1 = tmp.x + dx[i], dy1 = tmp.y + dy[i];
if (dy1<1 || dx1<1 || dy1>n || dx1>n)
continue;
else
{
if (map[dx1][dy1] < 0 && map[tmp.x][tmp.y] >= 0)
{
if (val[dx1][dy1] > val[tmp.x][tmp.y] + 2)
{
val[dx1][dy1] = val[tmp.x][tmp.y] + 2;
q.push({ dx1,dy1,val[dx1][dy1],map[tmp.x][tmp.y] });
continue;
}
}
else if (map[dx1][dy1] >= 0 && map[tmp.x][tmp.y] >= 0)
{
if (map[dx1][dy1] == map[tmp.x][tmp.y])
{
if (val[dx1][dy1] > val[tmp.x][tmp.y])
{
val[dx1][dy1] = val[tmp.x][tmp.y];
q.push({ dx1,dy1,val[dx1][dy1],map[dx1][dy1] });
continue;
}
}
else
{
if (val[dx1][dy1] > val[tmp.x][tmp.y] + 1)
{
val[dx1][dy1] = val[tmp.x][tmp.y] + 1;
q.push({ dx1,dy1,val[dx1][dy1],map[dx1][dy1] });
continue;
}
}
}
else if (map[dx1][dy1] >= 0 && map[tmp.x][tmp.y] < 0)
{
if (map[dx1][dy1] == tmp.color)
{
if (val[dx1][dy1] > tmp.cost)
{
val[dx1][dy1] = tmp.cost;
q.push({ dx1,dy1,val[dx1][dy1],map[dx1][dy1] });
continue;
}
}
else
{
if (val[dx1][dy1] > tmp.cost + 1)
{
val[dx1][dy1] = tmp.cost + 1;
q.push({ dx1,dy1,val[dx1][dy1],map[dx1][dy1] });
continue;
}
}
}
}
}
}
}
}
if (ans == 1e9)
cout << -1;
else
cout << ans;
}【模板】Johnson 全源最短路 建议直接当板子用
12:
这道题主要是在建图 我们假设一个2nx2m 的图 每个区域点的周围墙壁视作一个点 1代表连通 0 代表不连通
建图完毕后我们对于图中每一个点跑一次bfs 将其所在的区域标记 找到前两个答案
对于后两个 我们每一次将一个格子去除跑一次bfs找最大就好
细节比较多：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
const int maxn = 110;
int a[110][110];//储存图
int p[55][55];
bool vis[110][110];
int ans = 0, num = 0;
int n, m;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1, -1, 0, 0 };
int idx, idy;
void find(int x, int y)//{x,y}代表开头
{
queue<pair<int, int>>q;
int now = 1;
q.push({ x,y });//将起点储存
vis[x][y] = 1;
while (!q.empty())
{
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int x1 = x + dx[i], y1 = y + dy[i];//代表转移的情况
if (x1 >= 0 && x1 <= 2 * n&&y1 >= 0 && y1 <= 2 * m&&a[x1][y1] == 0 && vis[x1][y1] == 0)
{
if ((x1 + y1) % 2 == 0)
now++;
q.push({ x1,y1 });
vis[x1][y1] = 1;
}
}
}
if (now > ans)
{
idx = x, idy = y;
ans = now;
}
else if(now==ans)
{
if (y < idy)
{
idx = x, idy = y;
}
else if(y==idy)
{
if (x > idx)
{
idx = x, idy = y;
}
}
}
}
signed main()
{
int x;
cin >> m >> n;
for (int i = 0; i <= 2 * n; i++)
for (int j = 0; j <= 2 * m; j++)
a[i][j] = 1;
for (int i = 1; i <= 2 * n; i += 2)
{
for (int j = 1; j <= 2 * m; j += 2)
{
cin >> x;
a[i][j] = 0;
if (x % 2 == 0)
{
a[i][j - 1] = 0;
}
x /= 2;
if (x % 2 == 0)
{
a[i - 1][j] = 0;
}
x /= 2;
if (x % 2 == 0)
{
a[i][j + 1] = 0;
}
x /= 2;
if (x % 2 == 0)
{
a[i + 1][j] = 0;
}
}
}
for (int i = 1; i <= 2 * n; i++)
{
for (int j = 1; j <= 2 * m; j++)
{
if (a[i][j] == 0 && vis[i][j] == 0)
{
num++;
find(i, j);
}
}
}
memset(vis, 0, sizeof vis);
cout << num << endl << ans<<endl;
ans = 0;
for (int i = 1; i <= 2 * n; i++)
{
for (int j = 1; j <= 2 * m; j++)
{
if (a[i][j] == 1&&i%2!=j%2)
{
a[i][j] = 0;
find(i, j);
a[i][j] = 1;
memset(vis, 0, sizeof vis);
}
}
}
cout << ans-1 << endl;
if(idx%2)
cout << (idx+1)/2 << ' ' << idy/2 <<" E"<< endl;
else
{
cout << idx / 2+1 << ' ' << (idy + 1) / 2 << " N" << endl;
}
}
骑士精神：
一道A*的模板题：
使用原因在于题目有明确要求在15步以内 所以这就代表 我们可以利用迭代加深来进行处理 ：这类题的通解 A*的使用是为了经行剪枝经行优化
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
#define int long long
int d[6][6] = { {0,0,0,0,0,0},
{0,1,1,1,1,1},
{0,0,1,1,1,1},
{0,0,0,2,1,1},
{0,0,0,0,0,1},
{0,0,0,0,0,0} };//目标状态
int dx[8] = { 1,1,2,2,-1,-1,-2,-2 };//位移
int dy[8] = { 2,-2,1,-1,2,-2,1,-1 };
int map[10][10];//白色为0 黑色为1 空为2
string s[5];
bool falg = 0;//用来判断是否成功
int ju()
{
int cnt = 0;
for (int i = 1; i <= 5; i++)
{
for (int j = 1; j <= 5; j++)
{
if (map[i][j] != d[i][j])
cnt++;
}
}
return cnt;
}
void dfs(int x, int y, int f, int g)
{
int now=ju();//判断至少还要几步成功
if (now == 0)
{
falg = 1;
return;
}
if (now+g>f+1)
{
return;//代表不可能
}
for (int i = 0; i <= 7; i++)
{
int nowx = x + dx[i], nowy = y + dy[i];
if (nowx <= 0 || nowx > 5 || nowy <= 0 || nowy > 5)
continue;
swap(map[nowx][nowy], map[x][y]);
dfs(nowx, nowy, f, g + 1);
swap(map[nowx][nowy], map[x][y]);
}
}
void solve()
{
falg = 0;
int sx, sy;
char c;
for (int i = 1; i <= 5; i++)
{
for (int j = 1; j <= 5; j++)
{
cin >> c;
if (c== '*')
{
sx = i, sy = j;
map[i][j] = 2;
}
else if (c== '1')
{
map[i][j] = 1;
}
else
{
map[i][j] = 0;
}
}
}
//开始迭代加深:
for (int i = 1; i <= 15; i++) {
dfs(sx, sy, i, 0);
if (falg)
{
cout << i << endl;
return;
}
}
cout << -1 << endl;
return;
}
signed main()
{
int t;
cin >> t;
while (t--)
solve();
}P1491 集合位置：
次短路题目：我们先跑一次dij 处理完最短路 后再次基础上每次删掉一条边 每删一次跑一次dij
求得此时最短就是次短路了
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int inf = 1e9;
const int maxn = 210;
const int maxm = 40040;
struct node
{
int pos;
double dis;
bool operator<(const node&x)const
{
return x.dis < dis;
}
};
struct edge
{
int to, next;
double dis;
}e[maxm];
double ans = inf;
int x[maxn], y[maxn];//记录点
int head[maxn], cnt,n,m;
double dis[maxn];
int prev1[maxn];//记录前驱
bool vis[maxn];
void add(int u, int v, double dis)
{
e[++cnt].dis = dis;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
double far(int x1, int y1, int x2, int y2)
{
return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
void dij(int a,int b)//表示删掉ab之间的边
{
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++)
dis[i] =inf;
dis[1] = 0.0;
priority_queue<node>q;
q.push({ 1,0 });
while (!q.empty())
{
int u = q.top().pos;
q.pop();
if (vis[u])
continue;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].next)
{
int y = e[i].to;
if ((u == a && y == b) || (u == b && y == a))
continue;
if (dis[y] > dis[u] + e[i].dis)
{
if (a == -1 && b == -1)
prev1[y] = u;//记录前驱
dis[y] = dis[u] + e[i].dis;
if (!vis[y])
{
q.push({ y,dis[y] });
}
}
}
}
}
int main()
{
double dis1 = 0.0;
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> x[i] >> y[i];
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
dis1 = far(x[u], y[u], x[v], y[v]);
add(u, v, dis1);
add(v, u, dis1);
}
dij(-1, -1);//求最短路
int now = n;//最后一个点明确在n
while (prev1[now])
{
dij(prev1[now], now);
ans = min(ans, dis[n]);
now = prev1[now];
}
if (ans == inf)
cout << -1;
else
printf("%.2lf", ans);
}