本题为1月10日22寒假集训每日一题题解
题目来源:(未知)
题面
题目描述
给出一个图,起始点是1,结束点是N,边是双向的。求点1到点N的最短距离。哈哈,这就是标准的最短路径问题。
输入
测试数据第一行为一个整数t,表示有t组测试数据。
每组测试数据的第一行为两个整数N(1<=N<=200)和M(0<=M<=10000)。N表示图中点的数目,M表示图中边的数目。
下来M行,每行三个整数x,y,c表示点x到点y之间存在一条边长度为c。( $ x \neq y $,1<=c<=10000)
输出
每组测试数据输出一行,一个整数,即为点1到点N的最短距离。
如果点1和点N不连通则输出-1。
样例输入
4
2
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
样例输出
3
2
思路分析
如题所说,这就是标准的最短路径问题,且显然是一个无负权图.这种问题直接套用dijkstra算法
即可(关于SPFA,它已经死了).
这里我实现的是一个使用邻接表
的优先队列
优化的dijkstra算法
.
参考代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
/*
边对象
*/
struct edge
{
int to;
int cost;
};
typedef pair<int, int> P; // 优先队列中使用的二元组,first为路径长度,second为顶点编号
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector<vector<edge>> G(n, vector<edge>()); // 邻接表
// 输入数据,编号改为从0开始,构建邻接表
while (m--)
{
int from, to, cost;
cin >> from >> to >> cost;
from--;
to--;
G[from].push_back(edge{to, cost});
G[to].push_back(edge{from, cost}); // 注意是无向图,需要反过来再连一条边
}
int *d = new int[n]; // 各点到起点的目前的最短路
memset(d, 0x3f, sizeof(int) * n);
priority_queue<P, vector<P>, greater<P>> que; // 优先队列(小顶堆)
// 优先队列优化的dijkstra算法
d[0] = 0;
que.push(P{0, 0});
while (!que.empty())
{
P p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first)
continue;
for (int i = 0; i < G[v].size(); i++)
{
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost)
{
d[e.to] = d[v] + e.cost;
que.push(P{d[e.to], e.to});
}
}
}
cout << (d[n - 1] == 0x3f3f3f3f ? -1 : d[n - 1]) << "\n"; // 注意处理不连通的情况
delete d;
d = nullptr;
}
return 0;
}
标签:int,短路,问题,--,cost,que,简单,include From: https://www.cnblogs.com/geministar/p/zstu22_1_10.html"正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯" ---亚里士多德