最短路径问题 题解：c++
#include <iostream>
#include <set>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <string>
using namespace std;
//边结构体
struct Edge {
int u, v, w, p;
};
vector<Edge> vec;
vector<int> G[1005];
int dist[1005]; // 存放起点到 i 点的最短距离
int vis[1005]; // 标记是否访问过（是否已确定最短距离）
int p[1005]; // 存放路径，p[i] 表示到 i 的最短路径中 i 的前一个节点
int money[1005];
// 添加一条边
void addEdge(int u, int v, int w,int p) {
vec.push_back({u,v,w,p}); // 存入 edges
G[u].push_back(vec.size() - 1); // 在 G[u] 中记录这条边的下标
}
void spfa(int s){
queue<int> q;
for(int &i : dist) i = 9999999;
for(int &i : money) i = ...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
写错了xdm，else if 里面是这样的，这题的测试数据有问题，就算是把钱去掉也能过
else if(dist[e.v] == dist[u] + e.w){
if(money[e.v] > money[u] + e.p){
money[e.v] = money[u] + e.p;
p[e.v] = u;
if(!vis[e.v]){
vis[e.v] = 1;
q.push(e.v);
}
}
}