（经典算法 要熟练运用!）
题目大意
找最短路径，若路径长度相同，找最小花费。
AC代码
邻接矩阵
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#define INF 1000000000
#define MAXV 600
using namespace std;
struct node {
int v;
int dis;
int cost;
};
vector<node>G[MAXV];
int dis[MAXV], c[MAXV];
bool vis[MAXV] = { false };
int pre[MAXV];
int n;
void Dijkstra(int begin) {
fill(dis, dis + MAXV, INF);
fill(c, c + MAXV, INF);
dis[begin] = 0;
c[begin] = 0;
int i, j;
for (i = 0;i < n;i++) {
pre[i] = i;
}
for (i = 0;i < n;i++) {
int min = INF, u = -1;
for (j = 0;j < n;j++) {
if (vis[j] == false && dis[j] < min) {
min = dis[j];
u = j;
}
}
if (u == -1)return;
vis[u] = true;
for (j = 0;j < G[u].size();j++) {
int v = G[u][j].v;
if (vis[v] == false && dis[v] > dis[u] + G[u][j].dis) {
dis[v] = dis[u] + G[u][j].dis;
c[v] = c[u] + G[u][j].cost;
pre[v] = u;
}
else if (vis[v] == false && dis[v] == dis[u] + G[u][j].dis) {
if (c[v] > c[u] + G[u][j].cost) {
c[v] = c[u] + G[u][j].cost;
pre[v] = u;
}
}
}
}
return;
}
void DFS(int s, int v) {
if (v == s) {
printf("%d", s);
return;
}
DFS(s, pre[v]);
printf(" %d", v);
}
int main() {
int m, s, d;
scanf("%d%d%d%d", &n, &m, &s, &d);
int i, j;
int u, v;
for (i = 0;i < m;i++) {
node tempnode;
scanf("%d%d%d%d", &u, &v, &tempnode.dis, &tempnode.cost);
tempnode.v = v;
G[u].push_back(tempnode);
tempnode.v = u;
G[v].push_back(tempnode);
}
Dijkstra(s);
DFS(s, d);
printf(" %d %d", dis[d], c[d]);
return 0;
}
