dijkstra算法搞不明白

#include<stdio.h>
#define MAXN (int)1e5+7
int m, n, s, d;
typedef struct edge {
int to;//终点
int next;//下一条边
int s;//路长
int m;//money
}edge;
typedef struct pii
{
int s;//路长
int m;//费用
}pii;
edge edges[MAXN];
int cnt, head[MAXN];//head[i]为编号为i的城市所能到达的所有地区
short vis[MAXN];//蓝白点
pii dist[MAXN];
inline short blean(pii a, pii b);//a比b更符合要求
inline void add(int from, int to, int s, int m);//从哪里来,要到哪里去,边权多少
void dijkstra(int start);
void newdij(int start);
int main() {
for (int i = 0; i < MAXN; ++i) {
dist[i].m = 0xfffff;
dist[i].s = 0xfffff;
}
scanf("%d%d%d%d", &n, &m, &s, &d);
s++; d++;
for (int i = 1; i <= m; ++i) {
int a, b, s, m;
scanf("%d%d%d%d", &a, &b, &s, &m);
a++; b++;
add(a, b, s, m);
add(b, a, s, m);
}
dist[s].m = 0;
dist[s].s = 0;
dijkstra(s);
printf("%d %d\n", dist[d].s, dist[d].m);
return 0;
}
inline void add(int from, int to, int s, int m) {
++cnt;//新建一条边
edges[cnt].s = s;//边权
edges[cnt].m = m;
edges[cnt].to = to;
edges[cnt].next = head[from];//向前加边
head[from] = cnt;
}
short blean(pii a, pii b) {
if (a.s == b.s)return a.m < b.m;
return a.s < b.s;
}
void dijkstra(int start) {
if (start == -1)return;
vis[start] = 1;
for (int e = head[start]; e; e = edges[e].next) {
pii temp = dist[start];
temp.s += edges[e].s;
temp.m += edges[e].m;
if (blean(temp, dist[edges[e].to])) {
dist[edges[e].to] = temp;
}
}
pii min = { 0xfffff,0xfffff };
int mark = -1;
for (int i = 1; i <= n + 1; ++i) {
if (!vis[i] && blean(dist[i], min)) {
min = dist[i];
mark = i;
}
}
dijkstra(mark);
}
void newdij(int start) {
while (1) {
int mark = -1;
pii min = { 0xfffff,0xfffff };
for (int i = 1; i <= n + 1; ++i) {
if (!vis[i] && blean(dist[i], min)) {
min = dist[i];
mark = i;
}
}
if (mark == -1)break;
vis[mark] = 1;
for (int e = head[mark]; e; e = edges[e].next) {
pii tmp = { dist[mark].s + edges[e].s,dist[mark].m + edges[mark].m };
if (blean(tmp, dist[edges[e].to])) {
dist[edges[e].to] = tmp;
}
}
}
}

觉得排版奇怪的话可以看下图

再补一张题目

直接dfs吧

另外再补一下之前的dfs
pii dfs(int from, int to) {
pii re = { 4000,4000 };
pii end ={0,0};
if (from == to)return end;
if (vis[from])return re;//走回头路直接pass,和到终点的处理不一样
for (int i = head[from]; i; i = edges[i].next) {
vis[from] = 1;
pii tmp = dfs(edges[i].to, to);
tmp.first += edges[i].s;
tmp.second += edges[i].m;
if (blean(tmp, re)) {
re = tmp;
}
vis[from] = 0;
}
return re;
}

我觉得你写的有点…怪？
朴素 dijkstra 不需要递归，就 3 个 for 循环，大体思路如下：
for(1 to n) {
// 1. 找未访问过且 dist 最小的点 u，将其标记为已访问
for(1 to n){
...
}
// 2. 遍历以 u 为起点的所有边 (u, v)，松弛 dist[v]
for(edge in adj[u]){
...
}
}

这是我刚刚写的，可以参考一下。
我觉得你的代码还有一个问题就是命名有点随意，导致可读性不够高

for (int i = 0; i < n; ++i) {
int u = -1;
int mindist = INF, minpri = INF;
for (int j = 0; j <= n; ++j) {
if (!vis[j] && (dist[j] < mindist || dist[j] == mindist && pri[j] < minpri)) {
mindist = dist[j];
minpri = pri[j];
u = j;
}
}
if (u == -1)break;
vis[u] = 1;
for (int v = head[u]; v; v = edge[v].next) {
int vt = edge[v].to;
int newdist = dist[u] + edge[v].len;
int newpri = pri[u] + edge[v].pri;
if (dist[vt] > newdist || dist[vt] == newdist && pri[vt] > newpri) {
dist[vt] = newdist;
pri[vt] = newpri;
}
}
}

#include <stdio.h>
#define MAXN (int)1e6 + 7 // @ZXP4：这里改大一点
int m, n, s, d;
typedef struct edge {
int to; // 终点
int next; // 下一条边
int s; // 路长
int m; // money
} edge;
typedef struct pii {
int s; // 路长
int m; // 费用
} pii;
edge edges[MAXN];
int cnt, head[MAXN]; // head[i]为编号为i的城市所能到达的所有地区
short vis[MAXN]; // 蓝白点
pii dist[MAXN];
inline short blean(pii a, pii b); // a比b更符合要求
void add(int from, int to, int s,
int m); // 从哪里来,要到哪里去,边权多少 // @ZXP4：这里我把 inline 去掉了，不然本地编译过不了
void dijkstra(int start);
void newdij(int start);
int main() {
for (int i = 0; i < MAXN; ++i) {
dist[i].m = 0xfffff;
dist[i].s = 0xfffff;
}
scanf("%d%d%d%d", &n, &m, &s, &d);
s++;
d++;
for (int i = 1; i <= m; ++i) {
int a, b, s, m;
scanf("%d%d%d%d", &a, &b, &s, &m);
a++;
b++;
add(a, b, s, m);
add(b, a, s, m);
}
dist[s].m = 0;
dist[s].s = 0;
newdij(s);
printf("%d %d\n", dist[d].s, dist[d].m);
return 0;
}
inline void add(int from, int to, int s, int m) {
++cnt; // 新建一条边
edges[cnt].s = s; // 边权
edges[cnt].m = m;
edges[cnt].to = to;
edges[cnt].next = head[from]; // 向前加边
head[from] = cnt;
}
short blean(pii a, pii b) {
if (a.s == b.s)
return a.m < b.m;
return a.s < b.s;
}
void dijkstra(int start) {
if (start == -1)
return;
vis[start] = 1;
for (int e = head[start]; e; e = edges[e].next) {
pii temp = dist[start];
temp.s += edges[e].s;
temp.m += edges[e].m;
if (blean(temp, dist[edges[e].to])) {
dist[edges[e].to] = temp;
}
}
pii min = {0xfffff, 0xfffff};
int mark = -1;
for (int i = 1; i <= n + 1; ++i) {
if (!vis[i] && blean(dist[i], min)) {
min = dist[i];
mark = i;
}
}
dijkstra(mark);
}
void newdij(int start) {
while (1) {
int mark = -1;
pii min = {0xfffff, 0xfffff};
for (int i = 1; i <= n + 1; ++i) {
if (!vis[i] && blean(dist[i], min)) {
min = dist[i];
mark = i;
}
}
if (mark == -1)
break;
vis[mark] = 1;
for (int e = head[mark]; e; e = edges[e].next) {
pii tmp = {dist[mark].s + edges[e].s, dist[mark].m + edges[e].m}; // @ZXP4: 这里 edges[mark].m 改成 edges[e].m
if (blean(tmp, dist[edges[e].to])) {
dist[edges[e].to] = tmp;
}
}
}
}
改动的地方标注过了，用的是你的 newdij，那个递归的 dijkstra 没改