1129. 热浪 原题链接
算法思路：
最短路模板题，Dijkstra或SPFA均可过（注意是双向边）
堆优化Dijkstras算法:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int INF = 0x3f;
const int N = 2510, M = 22000;
int n, m;
int s, z;
int h[M];
int ne[M];
int e[M];
int w[M];
int dist[M];
int idx;
int st[M];
void add(int a, int b, int v)
{
e[idx] = b, ne[idx] = h[a], w[idx] = v, h[a] = idx ++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<PII,vector<PII>,greater<PII>>heap;
heap.push({0,s});
while (heap.size()){
auto it = heap.top();
heap.pop();
int u = it.second;
int distance = it.first;
if(st[u])
continue;
st[u] = 1;
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > distance + w[i]){
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
return dist[z];
}
int main()
{
cin >> n >> m >> s >> z;
memset (h, -1, sizeof h);
for (int i = 1; i <= m; i ++ ){
int a, b, v;
cin >> a >> b >> v;
add(a, b, v);
add(b, a, v);
}
cout << dijkstra() << endl;
return 0;
}
1128. 信使 原题链接
算法思路：
同样是最短路的模板题，但是求出起点到各个点的最短路后，需要求出其中的最大值，即为所需要的最少时间
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 500;
int g[N][N];
int dist[N];
int st[N];
int n, m;
int dijkstra()
{
int res = 0;
memset(dist, INF, sizeof dist);
dist[1] = 0;
for (int i = 1; i <= n; i ++ ){
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = 1;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
for (int i = 1; i <= n; i ++ )
if(dist[i] == INF)
return -1;
else
res = max(dist[i],res);
return res;
}
int main()
{
cin >> n >> m;
memset(g, INF, sizeof g);
for (int i = 1; i <= m; i ++ ){
int a, b, v;
cin >> a >> b >> v;
g[a][b] = g[b][a] = min(g[a][b], v);
}
cout << dijkstra() << endl;
return 0;
}
1127. 香甜的黄油 原题链接
算法思路：
需要找出一个牧场，满足到其它牧场距离之和最短，所以枚举每个牧场作为起点，计算所有牛到该牧场的最短距离之和
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5000;
int n,m,cows;
int cow[N];
int h[N];
int e[N];
int ne[N];
int idx;
int w[N];
void add(int a, int b, int v)
{
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int spfa(int x)
{
int dist[N];
int st[N];
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[x] = 0;
queue<int> q;
q.push(x);
st[x] = 1;
while (q.size()){
int u = q.front();
q.pop();
st[u] = 0;
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > dist[u] + w[i]){
dist[j] = dist[u] + w[i];
if (!st[j]){
st[j] = 1;
q.push(j);
}
}
}
}
int ans = 0;
for (int i = 1; i <= cows; i ++ ){
int j = cow[i];
if (dist[j] == INF)
return INF;
else
ans += dist[j];
}
return ans;
}
int main()
{
cin >> cows >> n >> m;
memset(h, -1, sizeof h);
memset(cow, 0 ,sizeof cow);
int x;
//cout << INF << endl;
for (int i = 1; i <= cows; i ++ ){
cin >> cow[i];
}
for (int i = 1; i <= m; i ++ ){
int a, b, v;
cin >> a >> b >> v;
add(a, b, v);
add(b, a, v);
}
int ans = INF;
for (int i = 1; i <= n; i ++ )
ans = min(ans, spfa(i));
cout << ans << endl;
return 0;
}
1126. 最小花费 原题链接
算法思路：
从A点出发，每经过一条路，每次乘路径上对应的权值$w$ ($0<w<=1$), 到达B后剩余100元，求最小损失。只需求出路径权重之积最大即可。
题目拓展：
一般最短路问题需要加上边权重，当需要每次乘边权重时，可以进行分类（证明使用$log$的乘积性质）：
-
$w>1$ : 转化为经过路径之积最小问题, Dijkstra与SPFA均可(边权为正)
-
$0<w<=1$ : 转化为经过路径之积最大问题,Dijkstra与SPFA均可(边权均为负，转化为正)
-
$w>0$ : 只能使用SPFA,转化为求路径之积最小问题(边权有负有正)
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2010;
int n,m;
double g[N][N];
double dist[N];
int st[N];
int A,B;
double dijkstra()
{
memset(dist, 0, sizeof dist);
dist[A] = 1;
for (int i = 1; i <= n; i ++ ){
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[j] > dist[t]))
t = j;
st[t] = 1;
for (int j = 1; j <= n; j ++ )
dist[j] = max(dist[j], dist[t] * g[t][j]);
}
return dist[B];
}
int main()
{
cin >> n >> m;
memset (g, 0, sizeof g);
for (int i = 1; i <= m; i ++ ){
int a, b, v;
scanf("%d%d%d",&a,&b,&v);
g[a][b] = g[b][a] = max(g[a][b], (100.0 - v) / 100);
}
cin >> A >> B;
double res = dijkstra();
printf("%.8f\n", 100 / res);
return 0;
}
920. 最优乘车 原题链接
算法思路：
题目难点在建图,由于计算最少换乘次数, 所以认为一条线路上的车站之间距离均为1, 每条路线上有$n$个站点,站点之间有 $C_{n}^{2}$ 条边, 且边权为1, 直接使用BFS即可。
题目拓展：
题目输入
比较坑, 使用#include<sstream>里的stringstream,将一行数据通过string读入stringstream, 再分个读入int中(读入时自动通过空格分隔且转换类型)
#include <iostream>
#include <queue>
#include <cstring>
#include <sstream>
using namespace std;
const int N = 510;
const int M = 200000;
int g[N][N];
int dist[N];
int n,m;
int stop[N]; //所有站点
void bfs()
{
memset(dist, -1, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
while (q.size()){
int u = q.front();
q.pop();
for (int i = 1; i <= n; i ++ )
if(g[u][i] && dist[i] == -1){
dist[i] = dist[u] + 1;
q.push(i);
}
}
}
int main()
{
cin >> m >> n;
string ss;
getline(cin, ss); //读入回车
for (int i = 1; i <= m; i ++ ){
getline(cin,ss); //读入ss
//将ss读入scin;
stringstream scin;
scin << ss;
int cnt = 0;
int p;
while (scin >> p){ //直接从scin读入p,同时转化为int
stop[cnt ++] = p;
//cout << p << endl;
}
//建图：
for (int j = 0; j < cnt; j ++ )
for (int k = j + 1; k < cnt; k ++ )
g[stop[j]][stop[k]] = 1;
}
bfs();
if (dist[n] == -1)
puts("NO");
else
cout << max(dist[n] - 1, 0) << endl;
return 0;
}
903. 昂贵的聘礼 原题链接
算法思路：
难点在建图, 我们提前假设一个虚拟原点,该点到其它各物品的距离为该物品的初始原价, 物品相互之间的距离为对应优惠价格, 这样为题转化为从原点出发, 到1号点的最短距离。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
const int INF = 0x3f3f3f3f;
int dist[N];
int l[N];
int n,m;
int g[N][N];
int st[N];
int dijkstra(int down, int up)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[0] = 0;
for (int i = 1; i <= n + 1; i ++ ){
int t = - 1;
for (int j = 0; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = 1;
for (int j = 0; j <= n; j ++ )
if (l[j] >= down && l[j] <= up)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
return dist[1];
}
int main()
{
cin >> m >> n;
memset(g,INF, sizeof g);
for (int i = 0; i <= n; i ++ )
g[i][i] = 0;
for (int i = 1; i <= n; i ++ ){
int p, cnt;
cin >> p >> l[i] >> cnt;
g[0][i] = min(g[0][i], p); //虚拟原点
//其它点
while (cnt -- ){
int id, cost;
cin >> id >> cost;
g[id][i] = min(g[id][i], cost);
}
}
int res = INF;
//枚举l[1]的m区间:
for (int i = l[1] - m; i <= l[1]; i ++ )
res = min(res, dijkstra(i, i + m));
cout << res << endl;
return 0;
}
