赛时第一眼看,是个无向图,求一个点到另外一个点的最小值,诶,这不裸的最短路嘛,然后兴高采烈地倒着跑了个 dijkstra
,喜提 \(30\) 分。仔细一看,\(w \le 100\),发现当 \(k > 100\) 时,生命就是永恒的,于是加了个剪枝,就过啦。
具体地,正常的最短路量有一个,本题有两个。于是我们定义 \(dist_{i,j}\) 表示当前魔力值为 \(i\) 走到 \(j\) 的最小生命值。每倒着走一条边,\(k\) 就多了 \(1\)。当 \(k > 100\) 时,往后无论怎么走,生命值都不会减少,\(k\) 就不用加了,直接跳过这个状态即可。其他和裸最短路没啥区别。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define PII pair<int, pair<int, int> >
#define x first
#define y second
const int N = 20010, M = 80010;
inline void in(int &x)
{
x = 0; bool f = 0; char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = 1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c & 15);
c = getchar();
}
x = f ? -x : x;
}
inline void out(int x)
{
if(x < 0) putchar('-'), x = -x;
if(x / 10) out(x / 10);
putchar((x % 10) | 48);
}
int n, m, s, t;
int h[N], e[M], ne[M], w[M], idx;
int dist[210][N], res[N];
bool st[210][N];
priority_queue<PII, vector<PII>, greater<PII> > q;
inline void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
return;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[0][s] =0;
q.push({0, {0, s}});
while (!q.empty())
{
PII p = q.top();
q.pop();
int id = p.second.second, k = p.second.first;
//对于一个 PII,first 表示最小生命值,second.first 表示当前魔法值,second.second 表示当前结点编号
if(st[k][id]) continue;
st[k][id] = 1;
if(k > 100) continue; //剪枝
for (int i = h[id]; ~i; i = ne[i])
{
int j = e[i];
if(dist[k + 1][j] > dist[k][id] + w[i] / (k + 1))
{
dist[k + 1][j] = dist[k][id] + w[i] / (k + 1);
q.push({dist[k + 1][j], {k + 1, j}});
} //更新状态
}
}
return;
}
int main()
{
memset(h, -1, sizeof h);
in(n); in(m); in(t); in(s); //倒着做
while (m -- )
{
int x, y, z;
in(x); in(y); in(z);
add(x, y, z); add(y, x, z);
}
dijkstra();
int ans = 0x3f3f3f3f;
for(int i = 0; i <= 101; i ++ ) ans = min(ans, dist[i][t]);
printf("%d\n", ans);
return 0;
}
标签:MGOI,dist,Simple,int,second,禁林,100,include,id
From: https://www.cnblogs.com/3042651coding/p/17612765.html