NC158. 单源最短路
描述
示例1
输入:
5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]
输出:
9
示例2
输入:
2,1,[[1,2,4]]
输出:
4
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-07-14
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
// write code here
vector<vector<pair<int, int>>> my_graph(n+1);
for(auto &i_vec : graph)
my_graph[ i_vec[0] ].push_back( {i_vec[1], i_vec[2]} );
vector<bool> used(n+1, false);
vector<int> record(n+1, INT_MAX);
int last_node_id = 1; record[1] = 0;
for(int k=1; k<=n; k++){
int val = record[last_node_id]; used[last_node_id] = true;
for(auto [node_id, len] : my_graph[last_node_id])
record[node_id] = min(record[node_id], val+len);
last_node_id = -1;
for(int j=1; j<=n; j++){
if( used[j] ) continue;
if(last_node_id == -1){ last_node_id = j; continue; }
if(record[j] < record[last_node_id])
last_node_id = j;
}
if(last_node_id == n) return record[n];
}
return -1;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-03-27
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
vector<Node> nodes(n + 1);
for(int i = 0; i < m; i ++)
{
vector<int> edge;
edge.emplace_back(graph[i][1]);
edge.emplace_back(graph[i][2]);
nodes[graph[i][0]].edges.emplace_back(edge);
}
vector<int> queue(n);//covered nodes' indices
int front;//pop here
int rear;//push here
queue[0] = 1;
front = rear = 0;
nodes[1].covered = true;
nodes[1].pathLength = 0;
while(front <= rear)
{
int nodeIndex = queue[front];
front ++;
for(vector<int>& edge : nodes[nodeIndex].edges)
{
int nextNodeIndex = edge[0];
int edgeLength = edge[1];
if(nodes[nextNodeIndex].covered)
{
if(nodes[nextNodeIndex].pathLength >
nodes[nodeIndex].pathLength + edgeLength)
{
nodes[nextNodeIndex].pathLength =
nodes[nodeIndex].pathLength + edgeLength;
}
}
else
{
nodes[nextNodeIndex].covered = true;
nodes[nextNodeIndex].pathLength =
nodes[nodeIndex].pathLength + edgeLength;
queue[++rear] = nextNodeIndex;
}
}
}
return nodes[n].pathLength;
}
struct Node
{
bool covered;
int pathLength;
vector<vector<int>> edges;//index 0 is the other node, index 1 is the edge length
Node():covered(false), pathLength(-1){}
};
};
C++ 解法, 执行用时: 2ms, 内存消耗: 392KB, 提交时间: 2021-07-27
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
vector<int> D(n+1, 0x3f3f3f3f);
D[1] = 0;
for (int i = 0; i < n; i++) {
bool isOk = true;
for (auto &g: graph) if (D[g[1]] > D[g[0]]+g[2]) {
isOk = false;
D[g[1]] = D[g[0]]+g[2];
}
if (isOk) break;
}
return D[n] == 0x3f3f3f3f?-1:D[n];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2021-08-04
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
using PII = pair<int, int>;//存储两个相同类型的值
const int INF = 0x3f3f3f3f;//32-bit int的最大值
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
// write code here
vector<vector<PII>> tab(n + 1);
for(const auto& i : graph)
tab[i[0]].emplace_back(i[1],i[2]);//和push_back大体相同
return dijal(tab,n);
}
int dijal(vector<vector<PII>>& tab,int n){
vector<int> pon(n + 1,0);
vector<int> lin(n + 1,INF);
lin[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;//创建一个优先队列
q.emplace(0,1);//在0位置插入1
while (not q.empty()){
const auto [dist, cur] = q.top(); q.pop();
if (pon[cur]++) continue;
for (const auto [nxt, w] : tab[cur])
if (dist + w < lin[nxt]) {
lin[nxt] = dist + w;
q.emplace(dist + w, nxt);
}
}
return lin[n];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2021-07-25
struct cmp {
template <typename T, typename U>
bool operator()(T const& left, U const& right) {
// 以 second 比较。输出结果为 Second 较小的在前; Second 相同时，先进入队列的元素在前。
if (left.second > right.second)
return true;
return false;
}
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
// write code here
vector<vector<int>> g(n + 1, vector<int>(n + 1, INT_MAX));
for (auto& x : graph) {
int a = x[0], b = x[1], c = x[2];
g[a][b] = min(g[a][b], c); //处理重边
}
return dijkstra(g, n, 1, n);
}
int dijkstra(vector<vector<int>>& g, int n, int start, int end) {
//基于bfs的dijkstra算法
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq; //优先级队列
pq.push(make_pair(start, 0));
vector<int> vis; //访问过的节点
map<int, int> parent; //最短路径中的父节点
vector<vector<pair<int, int>>> adj(n + 1); //前驱节点链表生成
for (int j = 1; j < g.size(); j++) {
for (int i = 1; i < g[j].size(); i++)
{
if (g[j][i] < INT_MAX)
adj[j].push_back(make_pair(i, g[j][i]));
}
}
//初始化distance
vector<int> distance(n + 1, INT_MAX);
distance[start] = 0;
for (auto& x : adj[start]) {
distance[x.first] = x.second;
}
while (!pq.empty()) {
pair<int, int> tmp = pq.top();
pq.pop();
int dist = tmp.second; //距上个点的距离
int node = tmp.first;
vis.push_back(node);
vector<pair<int, int>> next = adj[node];
for (auto& x : next) {
int i = 0;
for (auto& v : vis) {
if (x.first != v) {
i++;
}
if (i == vis.size()) {
if ((dist + x.second) <= distance[x.first]) {
pq.push(pair<int, int>(x.first, dist + x.second));
parent[x.first] = node;
distance[x.first] = dist + x.second;
}
}
}
}
}
return distance[end];
}
};