最短路

最短路

时间限制：4 sec 空间限制：256 MB

问题描述

给定一张 n 个点的无向带权图，节点的编号从 1 至 n，求从 S 到 T 的最短路径长度。

输入格式

第一行 4 个数 n,m,S, T，分别表示点数、边数、起点、终点。

接下来 m 行，每行 3 个正整数 u,v,w，描述一条 u 到 v 的双向边，边权为 w。

保证 1<=u,v<=n。

输格式

输出一行一个整数，表示 S 到 T 的最短路。

样例输入

样例输

样例文件下载（包含第二个样例）

数据范围

本题共设置 12 个测试点。

对于前 10 个测试点，保证 n<=2500，m<=6200，对于每条边有 w<=1000。这部分数据有梯度。

对于所有的 12 个测试点，保证 n<=100,000，m<=250,000。

提示

[本题是 Dijkstra 算法的模板练习题。]

[使用朴素的 Dijkstra 算法可以通过前 10 个测试点。]

[使用堆或 std::priority_queue 优化的 Dijkstra 算法可以通过所有测试点。]

代码

#include <iostream> #include<vector> #include<queue> #include <utility> #include <cstring>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */ const int N = 100005;

typedef pair<int, int> pii;

//graph:存放图,graph[i]表示的是节点i的出边,其中first存储到达的节点,second存储边权

//pq:辅助Dijkstra算法的优先队列

//flag:记录每个节点是否进行过松弛，1表示进行过，0表示未进行过

//mind:存储起点s到每个节点的最短路径长度vector<pii> graph[N];

priority_queue<pii, vector<pii>, greater<pii>> pq;//升序队列bool flag[N];

int mind[N];

// 这个函数用于计算答案（最短路）

// n：节点数目

// m：双向边数目

// U,V,W：分别存放各边的两端点、边权

// s,t：分别表示起点、终点

// 返回值：答案（即从 s 到 t 的最短路径长度）

int shortestPath(int n, int m, vector<int> U, vector<int> V, vector<int> W, int s, int t)

{

/* 请在这里设计你的算法 */

//初始化，清空pq,graph,mind,flag

while (!pq.empty())

pq.pop();

for (int i = 1; i <= n; ++i)

graph[i].clear();

memset(mind, 127, sizeof(mind));

memset(flag, 0, sizeof(flag));

//建图，连接图中各边

for (int i = 0; i < m; ++i)

{

graph[U[i]].push_back(make_pair(V[i], W[i]));//建立从起点为U[i]出发，到达V[i]

的权值为W[i]的边

graph[V[i]].push_back(make_pair(U[i], W[i]));

}

//设置起点的最短路为0，并将起点加入优先队列中

mind[s] = 0;

pq.push(make_pair(mind[s], s));

//执行Dijkstra算法

while (!pq.empty())//循环条件暂定，可能会存在错误

{

int u = pq.top().second;//取出堆顶元素

pq.pop();

if (!flag[u])//每个节点最多做一次松弛，如果flag[u]为1，说明此节点距离起点更

近，已经被访问过(即此节点已被激活)，此时应该跳过此节点(可视为此节点已经被划入与起点相连 的集合中)

{

flag[u] = 1;

for (vector<pii>::iterator it = graph[u].begin(); it != graph[u].end();

++it)//枚举所有u出发的边

{

int v = it->first, w = it->second;

if (mind[v] <= mind[u] + w)//若mind[v]距离原点更近，则说明

continue;

mind[v] = mind[u] + w;

pq.push(make_pair(mind[v], v));//将v伴随其最新的最短路长度加入优先队

列

}

}

}

return mind[t];

}

// ================= 代码实现结束 =================

int main() {

int n, m, s, t;

scanf("%d%d%d%d", &n, &m, &s, &t);

vector<int> U, V, W;

U.clear();

V.clear();

W.clear();

for (int i = 0; i < m; ++i) {

int u, v, w;

scanf("%d%d%d", &u, &v, &w);

U.push_back(u);

V.push_back(v);

W.push_back(w);

}

printf("%d\n", shortestPath(n, m, U, V, W, s, t));

return 0;

}