<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1129.热浪
德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪!!!
他们的德克萨斯长角牛吃起来不错,可是它们并不是很擅长生产富含奶油的乳制品。
农夫 $John$ 此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。
$John$ 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。
这些路线包括起始点和终点一共有 $T$ 个城镇,为了方便标号为 $1$ 到 $T$。
除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。
每条道路有一个通过费用(包括油费,过路费等等)。
给定一个地图,包含 $C$ 条直接连接 $2$ 个城镇的道路。
每条道路由道路的起点 $R_s$,终点 $R_e$ 和花费 $C_i$ 组成。
求从起始的城镇 $T_s$ 到终点的城镇 $T_e$ 最小的总费用。
输入格式
第一行: $4$ 个由空格隔开的整数: $T, C, T_s, T_e$;
第 $2$ 到第 $C+1$ 行: 第 $i+1$ 行描述第 $i$ 条道路,包含 $3$ 个由空格隔开的整数: $R_s, R_e, C_i$。
输出格式
一个单独的整数表示从 $T_s$ 到 $T_e$ 的最小总费用。
数据保证至少存在一条道路。
数据范围
$1 \le T \le 2500$,
$1 \le C \le 6200$,
$1 \le T_s,T_e,R_s,R_e \le T$,
$1 \le C_i \le 1000$
输入样例:
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例:
7
普通的最短路,注意代码细节
$yxc$ 大佬已经视频讲解讲得很清楚了,思路不过多赘述
上课前写完后发现,代码变量不是特别一样:
$n$:节点个数 $m$:边的个数 $s$:起点编号 $e$:中点编号
$d_i$:$distance$ 间距,表示 当前从起点到点 $i$ 的最短路径的最小值
$v_i$:$visit$ 访问,表示 当前有没有访问(更新)节点 $i$
定义结构体 $node$ 用来表示一条边,其中结构体中的 $to$ 表示 边的终点,$w$ 表示 边的权值
这里之所以不用 $pair$ 主要是因为复杂的题目一条边可能存 更多的信息,直接定义结构体更容易修改,所以不用
反正我也不会用$pair$ 来记录边的信息
最后定义一个向量 $vec_{i, j}$:用来存边(仅仅是笔者习惯,向量命名为 $vec$ ),表示 起点为 $i$ 的第 $j$ 条边 (这条边终点为 $vec_{i, j}.to$,权值为 $vec_{i, j}.w$ )
具体内容见代码:
c++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2000009, INF = 1e9;
struct node
{//node表示一条边
int to, w;
//to表示路径终点,w表示路径权值
bool operator <(const node &x) const
{
if(w == x.w) return to > x.to;
else return w > x.w;
}
};
bool v[N];//记录节点有没有被访问
int d[N];//记录每一个节点到起点最短路
int n;//节点个数
int m;//边的个数
int s, e;//起点与终点
vector <node> vec[N];
priority_queue <node> q;//优先队列
void dijkstra(int x)
{
for(int i = 1;i <= n;++ i) d[i] = INF, v[i] = false;
//一开始,所有边都不与起点连通
d[x] = 0;//起点到自己的距离为0
q.push((node){x, 0});//起点入队
while(!q.empty())//当优先队列里还有变
{
node e = q.top(), tmp; q.pop();//
v[e.to] = true;
for(int i = 0;i < vec[e.to].size();++ i)
{
tmp = vec[e.to][i];
if(v[tmp.to]) continue;
if(d[tmp.to] > d[e.to] + tmp.w)
{
d[tmp.to] = d[e.to] + tmp.w;
// cout << e.to << " " << tmp.to << " " << d[tmp.to] << endl;
q.push((node) {tmp.to, d[tmp.to]});
}
}
}
return;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m >> s >> e;
for(int i = 1, u, v, w;i <= m;++ i)
{//u代表路径起点,v代表路径终点,w代表路径长度
cin >> u >> v >> w;
vec[u].push_back((node) {v, w});//建边
vec[v].push_back((node) {u, w});//建反边
//因为是无向图,建两条边
}
dijkstra(s);//从起点开始
cout << d[e] << endl;//输出答案
return 0;
}