最短路径问题

//首先这个题目按照题意是不能用floyd算法的，因为点的个数最大为1000，而floyd算法的复杂度为n*n*n，如果正式上机会超时。
//既然已经决定要用迪杰斯特拉算法，那么首先考虑存储方式，这个题目即可以邻接链表，也可以邻接矩阵。两种方法都给出，请斧正。
//邻接矩阵法：
/*
#include<stdio.h>
#define N 1001
#define MAX 110000000
int dis[N][N]; //表示距离的邻接矩阵
int cost[N][N];  //表示花费的邻接矩阵
int adis[N];  //单点到其他点的距离最小值
int acost[N];  //在距离最小的前提下的花费最小值
bool mark[N];  //是否已经在集合中
void init(int n)  //初始化各数组
{
    for(int i=1;i<=n;i++)  //将距离和花费均设为不可达 即最大。
    {
        adis[i]=MAX;
        acost[i]=MAX;
    }
    for(int i=1;i<=n;i++)  //所有点均不在集合上。
        mark[i]=false;
    for(int i=1;i<=n;i++){  //对于邻接矩阵，i==j设为0，自己到自己必定不需要消耗，不相等设为无限大
        for(int j=1;j<=n;j++){
            if(i==j) {
                dis[i][j]=0;
                cost[i][j]=0;
            }
            else
            {
                dis[i][j]=MAX;
                cost[i][j]=MAX;
            }
        }
    }
}
int main()
{
    int n,m;  //点数，边数
    int start,over; //起点，终点。
    while(~scanf("%d%d",&n,&m))  
    {
        if(n==0&&m==0) break;  //全为0，结束。
        init(n);  //调用初始化函数。
        while(m--)  //读取各边
        {
            int a,b,d,p;  //分别是起点终点距离花费
            scanf("%d%d%d%d",&a,&b,&d,&p);  //读取
            if(dis[a][b]>d)  //邻接矩阵存取无向图，将对称局域设为相同。
            {
                dis[a][b]=d;   //题目给的是有向图的点，强行变为无向图要注意对称区域值相同。
                dis[b][a]=d;
                cost[a][b]=p;
                cost[b][a]=p;
            }   
            else if(dis[a][b]==d&&cost[a][b]>p)  //如果距离相同，且花费更小，也选用
            {
                cost[a][b]=p;
                cost[b][a]=p;
            }
        }
        scanf("%d%d",&start,&over);  //读取起点 终点。
        adis[start]=0;  //将起点距离设为0
        acost[start]=0;  //起点花费设为0
        mark[start]=true;  //起点设为可达，放入集合。
        int newp=start;  //最新点为起点。
        for(int i=1;i<n;i++)  //遍历次数，为n-1次，就可以将所有点都遍历一遍，因为第一个已经有了
        {
            for(int j=1;j<=n;j++)  //遍历各点，寻找距离最新点距离最小的点。距离相等且花费最小。
            {
                int tmpc=cost[newp][j];  //这里不论行数为newp 还是列数为newp没区别，因为是相等的
                int tmpd=dis[newp][j];
                if(mark[j]==true) continue;  //已经加入集合，跳过。
                if(adis[j]>adis[newp]+tmpd)   //如果距离小于原来的距离，更新消耗和距离！！
                {
                    adis[j]=adis[newp]+tmpd;
                    acost[j]=acost[newp]+tmpc;
                }
                else if(adis[j]==adis[newp]+tmpd&&acost[j]>acost[newp]+tmpc)  //如果距离相等但是消耗更小，更新消耗
                   {
                       acost[j]=acost[newp]+tmpc;
                   }
            }
            int min=MAX;  //选择符合条件的（距离最短，距离相等花费最少）的点
            for(int j=1;j<=n;j++)  //遍历各点
            {
                if(mark[j]==true) continue;  //已经在集合里，跳过
                if(adis[j]==MAX) continue;  //不可达，跳过
                if(adis[j]<min) {  //选出最小的那个点 为j
                    min=adis[j];
                    newp=j;  //更新newp；
                }
            }
            mark[newp]=true;  //将newp设为可达
        }
        printf("%d %d\n",adis[over],acost[over]);  //最后输出距离和花费
    }
    return 0 ;
}*/
//下面所用的是邻接链表存储法。方法大同小异
#include<stdio.h>
#include<vector>
#define N 1001
using namespace std;
struct E{
    int next;
    int cost;
    int dis;
};
vector<E> edge[N];
bool mark[N];
int dis[N];
int cost[N];
int main(){
    int m,n;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(m==0&&n==0) break;
        int i;
        for(i=1;i<=n;i++){
                edge[i].clear();
                dis[i]=-1;
                cost[i]=0;
                mark[i]=false;
        }
        while(m--){
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&d,&c);
            E tmp;
            tmp.dis=d;
            tmp.cost=c;
            tmp.next=b;
            edge[a].push_back(tmp);
            tmp.next=a;
            edge[b].push_back(tmp);
        }
        int s,t;
        scanf("%d%d",&s,&t);
        int newP=s;
        mark[s]=true;
        dis[s]=0;
        for(i=1;i<n;i++){
            for(int j=0;j<edge[newP].size();j++){
                int next=edge[newP][j].next;
                int c=edge[newP][j].cost;
                int d=edge[newP][j].dis;
                if(mark[next]==true) continue;
                if(dis[next]==-1||dis[next]>dis[newP]+d||dis[next]==dis[newP]+d&&cost[next]>cost[newP]+c){
                    dis[next]=dis[newP]+d;
                    cost[next]=cost[newP]+c;
                }
            }
            int min=233333333;
            for(int j=1;j<=n;j++)
                if(mark[j]==false&&dis[j]!=-1&&dis[j]<min){
                    min=dis[j];
                    newP=j;
                }
            mark[newP]=true;
        }
        printf("%d %d\n",dis[t],cost[t]);
    }
    return 0;
}

#include <stdio.h>
#include <vector>

using namespace std;

struct E{
    int d,p;
    int next;
};

vector<E> edge[1001];
int dis[1001];
int spend[1001];
bool mark[1001];

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0) break;
        int a,b,d,p;
        for(int i=1;i<=n;i++)
            edge[i].clear();
        
        while(m--){
            scanf("%d%d%d%d",&a,&b,&d,&p);
            E tmp;
            tmp.d=d;
            tmp.p=p;
            tmp.next=b;
            edge[a].push_back(tmp);
            tmp.next=a;
            edge[b].push_back(tmp);
        }
        
        for(int i=1;i<=n;i++){
            dis[i]=-1;
            spend[i]=0;
            mark[i]=false;
        }
        int s,t;
        scanf("%d%d",&s,&t);
        int newP=s;
        mark[s]=true;//从s出发
        dis[s]=0;
       //edge[i][j]是一个二维数组用邻接链表的形式表示地图 i从1开始是因为 顶点编号从1开始
        for(int i=1;i<n;i++){//s 已在 Path集合中 遍历剩余n-1个顶点
            for(int j=0;j<edge[newP].size();j++){//vector<E> edge[1001] 语句 得到的是一个二维数组 每个数组单元存储类型为E  
                //由edge【newP】.size()得到newP的相邻顶点数  
                int d=edge[newP][j].d;
                int p=edge[newP][j].p;
                int next=edge[newP][j].next;
                if(mark[next]==true) continue;
                if(dis[next]==-1||dis[newP]+d<dis[next]||dis[next]==dis[newP]+d && spend[next]>spend[newP]+p){
                    //当 next顶点不可达||Souce到next的距离大于当前从Souce到newP到next的距离||多条最短路径但当前的花费少
                    dis[next]=dis[newP]+d;
                    spend[next]=spend[newP]+p;
                }
            }
            
            int min=123123123;
            for(int j=1;j<=n;j++){//选择离souce最近的点 为newP
                if(mark[j]==true) continue;
                if(dis[j]==-1) continue;
                if(dis[j]<min){
                    min=dis[j];
                    newP=j;
                }
            }
            mark[newP]=true;
        }
        printf("%d %d\n",dis[t],spend[t]);
      
    }
    return 0;
}

/*
*author Sun x y
*2021.1.20
*1 用Floyd可能会超时，毕竟是全源。用Dijstra 和 PSFA(优化)均可以。
*2 重点是存储方式的选择 ， n 1e3,m 1e6些许稠密，但是题目的数据可以存在两点之间多条
*无向边的情况，这就给邻接表带来很大优势。
*3 直接基于基本的PSFA(也可优化)，在搜索到相同的最短距离时，优化最小花费(在最短距离可以优化时，
*必须同步优化最小花费，因为求的就是最短距离基础上的最小花费)。
*
*/


#include<bits/stdc++.h>

using namespace std;

struct L
{
    int dis, wei;    //一条边的距离和花费
    L(int _dis, int _wei):dis(_dis), wei(_wei){}
};

const int maxn = 1e3;
const int INF = 0x3f3f3f3f;
vector<pair<int, L> > G[maxn+5];     //无向图邻接表
int d[maxn+5], w[maxn+5], num[maxn+5];  //源点最短距离数组，最短路上的最小花费数组，PSFA入队次数数组
bool inq[maxn+5];   //是否在队列
int n, m, s, t;     //点数 边数 起点 终点

void Create()    //创建无向图的邻接表   (题目的数据允许两个点有多条边  所以用邻接表更好而不是邻接矩阵)
{
    int u, v, d, w;
    for(int i = 0;i < m; i++)
    {
        cin >> u >> v >> d >> w;
        G[u].push_back(make_pair(v, L(d, w)));
        G[v].push_back(make_pair(u, L(d, w)));
    }
}

bool PSFA_SLF()      //PSFA的双端队列优化 求解最短路 和 最短路的最小花费
{                             
    fill(d, d+n+1, INF);
    fill(w, w+n+1, INF);
    fill(num, num+n+1, 0);
    fill(inq, inq+n+1, false);

    deque<int> dq;
    dq.push_back(s); inq[s] = true; num[s]++; d[s] = 0; w[s] = 0;

    while(!dq.empty())
    {
        int u = dq.front(); dq.pop_front(); inq[u] = false;
        for(int i = 0;i < G[u].size(); i++)
        {
            int v = G[u][i].first;
            int dis = G[u][i].second.dis, wei = G[u][i].second.wei;
            if(d[u]+dis == d[v])
            {
                if(w[u]+wei < w[v]) w[v] = w[u]+wei;   //1  若要打印最短路的最小花费 在1、2 加一个pre[v] = u即可
            }
            else if(d[u]+dis < d[v])
            {
                d[v] = d[u]+dis; w[v] = w[u]+wei;    //2
                if(inq[v] == false)
                {
                    if(dq.empty()) dq.push_back(v);
                    else if(d[v] <= d[dq.front()]) dq.push_front(v);
                    else dq.push_back(v);
                    inq[v] = true; num[v]++;     
                    if(num[v] >= n) return false;    //存在源点可达的负环
                }
            }
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n >> m && n && m)
    {
        Create(); cin >> s >> t;
        PSFA_SLF();
        cout << d[t] << " " << w[t] << "\n";
    }
    return 0;
}

#include <cstdio>
(802)#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge;
typedef vector<vector<Edge>> AdjList;
typedef pair<int, int> Cost;  // distance & price
Cost operator+(const Cost& c1, const Cost& c2) {
    return make_pair(c1.first + c2.first, c1.second + c2.second);
}
struct Edge {
    int to;
    Cost cost;
};
struct Point {
    int idx;
    Cost cost;
    bool operator<(Point p) const { return cost > p.cost; }
};
Cost Dijkstra(const AdjList& graph, int from, int to) {
    vector<Cost> costTable(graph.size(), make_pair(INF, INF));
    priority_queue<Point> pointQueue;
    pointQueue.push(Point{from, make_pair(0, 0)});
    while (!pointQueue.empty()) {
        Point cur = pointQueue.top();
        pointQueue.pop();
        if (cur.cost <= costTable[cur.idx]) {
            costTable[cur.idx] = cur.cost;
            for (const auto& edge : graph[cur.idx]) {
                if (costTable[cur.idx] + edge.cost < costTable[edge.to]) {
                    costTable[edge.to] = costTable[cur.idx] + edge.cost;
                    pointQueue.push(Point{edge.to, costTable[edge.to]});
                }
            }
        }
    }
    return costTable[to];
}
int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        AdjList graph(n + 1);
        while (m--) {
            int from, to, len, price;
            scanf("%d%d%d%d", &from, &to, &len, &price);
            graph[from].push_back(Edge{to, make_pair(len, price)});
            graph[to].push_back(Edge{from, make_pair(len, price)});
        }
        int s, t;
        scanf("%d%d", &s, &t);
        Cost cost = Dijkstra(graph, s, t);
        printf("%d %d\n", cost.first, cost.second);
    }
    return 0;
}

#include <stdio.h>
#define INF 1E9
#define N 1001
//INF是自定义的"无穷大"，N是图的最大尺寸
int Dist[N][N];//距离
int Cost[N][N];//花费

void Init(int n)
{//初始化图
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i==j) Cost[i][j]=Dist[i][j]=0;
            else Cost[i][j]=Dist[i][j]=INF;
        }
    }
}

int Add(int a, int b)
{//两个整数相加(防溢出)，如果有一个是无穷大，那和也是无穷大
    return (a==INF || b==INF)? INF : a+b;
}

void Floyd(int n, int from, int to)
{//用Floyd算法求出最短路径并输出
    for(int k=1; k<=n; k++)//途经的点
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=i; j<=n; j++)//既然是无向图，那就只遍历半张图
            {
                if(Add(Dist[i][k], Dist[k][j])<Dist[i][j])
                {//如果经过k能让距离更短，那就修改i到j的距离和花费
                    Dist[i][j]=Dist[j][i]=Add(Dist[i][k], Dist[k][j]);
                    Cost[i][j]=Cost[j][i]=Add(Cost[i][k], Cost[k][j]);
                }
                else if(Dist[i][j]==Add(Dist[i][k], Dist[k][j])
                        &&Add(Cost[i][k], Cost[k][j])<Cost[i][j])
                {//经过k距离不变但花销更少，那就修改i到j的花费
                    Cost[i][j]=Cost[j][i]=Add(Cost[i][k], Cost[k][j]);
                }
            }
        }
    }
    printf("%d %d\n", Dist[from][to], Cost[from][to]);//输出结果
    return;
}

int main()
{
    int m, n, from, to, d, p;
    while(scanf("%d %d", &n, &m)!=EOF)
    {
        if(m==0&&n==0) break;
        Init(n);//初始化
        while(m--)//读取输入的边的信息
        {
            scanf("%d%d%d%d", &from, &to, &d, &p);
            if(d<Dist[from][to])
            {//距离短一定收录
                Dist[from][to]=Dist[to][from]=d;
                Cost[from][to]=Cost[to][from]=p;
            }
            else if(d==Dist[from][to]&&p<Cost[from][to])
            {//距离一样但是花销更小那也要收录
                Dist[from][to]=Dist[to][from]=d;
                Cost[from][to]=Cost[to][from]=p;
            }
        }
        scanf("%d %d", &from, &to);
        Floyd(n ,from, to);//计算最短路径并输出
    }
    return 0;
}

#include <stdio.h>
#include <algorithm>
using namespace std;

struct E {
    int length;
    int cost;
} edge[1000][1000];


int main() {
    int n,m,s,t;
    while(scanf("%d%d",&n,&m)!=EOF) {
        if(n==0&&m==0) break;
        else {
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    if(i==j) {
                        edge[i][j].length=0;
                        edge[i][j].cost=0;
                    } else {
                        edge[i][j].length=9999;
                        edge[i][j].cost=9999;
                    }
                }
            }
            for(int i=0; i<m; i++) {
                int a,b,c,d;
                scanf("%d%d%d%d",&a,&b,&c,&d);
                if(edge[a][b].length>c){
                    edge[a][b].length=edge[b][a].length=c;
                    edge[a][b].cost=edge[b][a].cost=d;
                }
            }
            scanf("%d%d",&s,&t);
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    for(int k=1; k<=n; k++) {
                        if(edge[i][k].length+edge[k][j].length>edge[i][j].length) continue;
                        else if(edge[i][k].length+edge[k][j].length==edge[i][j].length) {
                            if(edge[i][k].cost+edge[k][j].cost<edge[i][j].cost) {
                                edge[i][j].cost=edge[i][k].cost+edge[k][j].cost;
                            }
                        } else {
                            edge[i][j].cost=edge[i][k].cost+edge[k][j].cost;
                            edge[i][j].length=edge[i][k].length+edge[k][j].length;
                        }
                    }
                }
            }
        }
        printf("%d %d\n",edge[s][t].length,edge[s][t].cost);
    }
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
class Edge{
    int next;
    int dist;
    int cost;
    public Edge(int next,int dist,int cost){
        this.next = next;
        this.dist = dist;
        this.cost = cost;
    }
}

class Vertex{
    int num;
    ArrayList<Edge> edge;
    public Vertex(int num){
        this.num = num;
        this.edge = new ArrayList<Edge>();
    }
}

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            if(n==0)
                break;
            int m = in.nextInt();
            Vertex[] list = new Vertex[n+1];
            for(int i=1;i<=n;i++)
                list[i] = new Vertex(i);
            
            for(int i=0;i<m;i++){
                int a = in.nextInt();
                int b = in.nextInt();
                int dist = in.nextInt();
                int cost = in.nextInt();
                list[a].edge.add(new Edge(b, dist, cost));
                list[b].edge.add(new Edge(a, dist, cost));
            }
            int s = in.nextInt();
            int t = in.nextInt();
            boolean[] marked = new boolean[n+1];
            int[] cost = new int[n+1];
            int[] dist = new int[n+1];
            for(int i=1;i<=n;i++){
                cost[i] = Integer.MAX_VALUE;
                dist[i] = -1;
                marked[i] = false;
            }
            dist[s] = 0;
            cost[s] = 0;
            marked[s] = true;
            int p = s;
            for(int i=1;i<=n;i++){
                for(int j=0;j<list[p].edge.size();j++){
                    int next = list[p].edge.get(j).next;
                    int c = list[p].edge.get(j).cost;
                    int d = list[p].edge.get(j).dist;
                    if(marked[next]==true) continue;
                    if(dist[next]==-1 || dist[next]>dist[p]+d || dist[next]== dist[p]+d && cost[next]>cost[p]+c){
                        dist[next] = dist[p] + d;
                        cost[next] = cost[p] + c;
                    }
                }
                int min = Integer.MAX_VALUE;
                for(int j=1;j<=n;j++){
                    if(marked[j]==true) continue;
                    if(dist[j]==-1) continue;
                    if(dist[j]<min){
                        min = dist[j];
                        p = j;
                    }
                }
                marked[p] = true;
            }
            System.out.printf("%d %d\n", dist[t],cost[t]);
        }
    }
}

比较坑的一点是同两个点之间有可能输入几条路径，需要在获取长度时判断是否比已有长度小（长度在初始化时需给一个最大值）

#include <cstdio>
#include<cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
const int INF = 0xfffffff;
int G[N][N],C[N][N];
int d[N],c[N];
int vis[N];
int n,m;
void Dijkstra(int s){     fill(d,d+N,INF);     fill(c,c+N,INF);     memset(vis,0,sizeof(vis));      d[s] = 0;     c[s] = 0;     for(int i = 0; i <= n; i++){         int u = -1,MIN = INF;         for(int j = 0; j <= n; j++){             if(vis[j] == 0&& d[j] < MIN){                 u = j;                 MIN = d[j];             }         }         if(u == -1) return; //s点无法到达剩余顶点          vis[u] = 1;         for(int v = 0; v <= n; v++){             if(vis[v] == 0 && G[u][v] != INF){                 if(d[u] + G[u][v] < d[v]){                     d[v] = d[u] + G[u][v];                     c[v] = c[u] + C[u][v];                 }else if(d[u] + G[u][v] == d[v]&&c[u] + C[u][v] < c[v]){                     c[v] = c[u] + C[u][v];                 }             }         }      }      }
int main(){     int a,b,w,p,st,ed;     while(scanf("%d%d",&n,&m) != EOF){         if(n==0&&m==0) break;         fill(G[0],G[0]+N*N,INF);         fill(C[0],C[0]+N*N,INF);         for(int i = 0; i < m; i++){             scanf("%d%d%d%d",&a,&b,&w,&p);             //下面这一步是核心，应该保证接收的图是最优的，再进一步做优化             if(w < G[a][b])
            {
                G[a][b] = G[b][a] = w;
                C[a][b] = C[b][a] = p;
            }
            else if(w == G[a][b] && p < C[a][b]){
                    C[a][b] = C[b][a] = p;
                 }             //至此，坑点结束         }         scanf("%d%d",&st,&ed);         Dijkstra(st);         printf("%d %d\n",d[ed],c[ed]);     }          return 0;
} 

#include<bits/stdc++.h>
using namespace std;

const int Max=1000;
const int INF=INT_MAX;

struct Edge{
    int to;
    int l;
    int p;
    Edge(int x,int y,int z):to(x),l(y),p(z){
    }
};

struct Point{
    int n;
    int d;
    Point(int x,int y):n(x),d(y){
    }
    bool operator < (const Point & a) const {
        return d>a.d;
    }
};

vector<Edge> graph[Max];
int dis[Max];
int price[Max];

void Dijkstra(int s){
    priority_queue<Point> q;
    dis[s]=0;
    price[s]=0;
    q.emplace(Point(s,dis[s]));
    while(!q.empty()){
        int u=q.top().n;
        q.pop();
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i].to;
            int l=graph[u][i].l;
            int p=graph[u][i].p;
            if(dis[v]==dis[u]+l&&price[v]>price[u]+p||dis[v]>dis[u]+l){
                dis[v]=dis[u]+l;
                price[v]=price[u]+p;
                q.emplace(v,dis[v]);
            }
        }
    }
    return ;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0){
            break;
        }
        memset(graph,0,sizeof(graph));
        fill(dis,dis+n+1,INF);
        fill(price,price+n+1,INF);
        while(m--){
            int from,to,d,p;
            cin>>from>>to>>d>>p;
            graph[from].emplace_back(Edge(to,d,p));
            graph[to].emplace_back(Edge(from,d,p));
        }
        int s,t;
        cin>>s>>t;
        Dijkstra(s);
        cout<<dis[t]<<" "<<price[t]<<endl;
    }
    return 0;
}

一开始，只添加了一条边，报错。每条数据需要添加两个边。

import sys
from collections import defaultdict
import heapq
class Edge:
    def __init__(self, to, dis, cost):
        self.to = to
        self.dis = dis
        self.cost = cost
class Point:
    def __init__(self, index, weight):
        self.index = index
        self.weight = weight

    def __lt__(self, other):
        return self.weight < other.weight
graph_table = {}
dis_table = [sys.maxsize for i in range(1001)]
cost_table = [sys.maxsize for i in range(1001)]
def dijkstra(start):
    store_list = []
    dis_table[start] = 0
    cost_table[start] = 0
    heapq.heappush(store_list, Point(start, dis_table[start]))
    while len(store_list) > 0:
        point = heapq.heappop(store_list)
        via = point.index
        neighbour = graph_table.get(via, [])
        sz = len(neighbour)
        for i in range(sz):
            to =  neighbour[i].to
            dis = neighbour[i].dis
            cost = neighbour[i].cost
            if dis_table[to] > dis_table[via] + dis or (dis_table[to] == dis_table[via] + dis and cost_table[to] > cost_table[via] + cost):
                dis_table[to] = dis_table[via] + dis
                cost_table[to] = cost_table[via] + cost
                heapq.heappush(store_list, Point(to, dis_table[to]))
count = 0
for line in sys.stdin:
    a = line.split()
    array = []
    if 0 == count:
        count = 1
        continue
    if len(a) == 4:
        start = int(a[0])
        to = int(a[1])
        dist = int(a[2])
        cost = int(a[3])
        neigh = graph_table.get(start, None)
        edge = Edge(to, dist, cost)
        if neigh is None:
            graph_table.update({start: [edge]})
        else:
            neigh.append(edge)

        edge = Edge(start, dist, cost)
        neigh = graph_table.get(to, None)
        if neigh is None:
            graph_table.update({to: [edge]})
        else:
            neigh.append(edge)

    if len(a) ==2:
        start = int(a[0])
        to = int(a[1])
        if 0 == start and 0 == to:
            break
        else:
            dijkstra(start)
            dis = int(dis_table[to])
            cost = int(cost_table[to])
            print(f"{dis} {cost}")

Dijkstra判断最小路径时注意花费

#include <iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<cstring>
#include<climits>
using namespace std;
#define INF 100000
struct Edge{
    int u;
    int v;
    int length;
    int money;
    Edge(int _u,int _v,int _length,int _money){
        u=_u;v=_v;length=_length;money=_money;
    }
};
struct point{
    int to;//终点
    int disance;
    point(int _to,int _disance){
       to=_to;disance=_disance;
    }
};
bool operator <(point l,point r){
    return l.disance>r.disance;
}
int dis[1001];//距离花费
int cost[1001];
vector<Edge>graph[1001];
void Dijkstra(int s){
    priority_queue<point> mpq;
    dis[s]=0;cost[s]=0;
    mpq.push(point(s,dis[s]));
    while (!mpq.empty()) {
        int temp=mpq.top().to;//距离最近的点
        mpq.pop();
        for(int i=0;i<graph[temp].size();i++){
            int v=graph[temp][i].v;
            int length=graph[temp][i].length;
            int money=graph[temp][i].money;
            if((dis[v]==dis[temp]+length&&cost[v]>cost[temp]+money)
            ||dis[v]>dis[temp]+length){
                dis[v]=dis[temp]+length; //花费和长度都需要判断
                cost[v]=cost[temp]+money;
                mpq.push(point(v,dis[v]));
            }
        }
    }
    return;
}
int main() {
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        int a,b,d,p;
        if(0==n&&0==m){
            break;
        }
        memset(graph, 0, sizeof(graph)); //图初始化
        fill(dis, dis + n + 1, INF); //距离初始化为无穷
        fill(cost, cost + n + 1, INF); //花费初始化为无穷
        for(int i=0;i<m;i++){
            scanf("%d%d%d%d",&a,&b,&d,&p);
            graph[a].push_back(Edge(a,b,d,p));//两个点都入图
            graph[b].push_back(Edge(b,a,d,p));
        }
        int s,t;
        scanf("%d%d",&s,&t);//起点终点
        Dijkstra(s);
        printf("%d %d\n",dis[t],cost[t]);
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

struct Edge {
	int u;
	int v;
	int weight;
	int cost;
	Edge(int _u, int _v, int _weight, int _cost) {
		u = _u;
		v = _v;
		weight = _weight;
		cost = _cost;
	}
};

struct PQNode {
	int u;  //结点的编号
	int distance;  //源点到这个点的距离
	int cost;  //源点到这个点的花费
	PQNode(int _u, int _distance, int _cost) {
		u = _u;
		distance = _distance;
		cost = _cost;
	}
};

bool operator < (PQNode lhs, PQNode rhs) {  //运算符重载 
	if (lhs.distance == rhs.distance) {
		return lhs.cost > rhs.cost;
	}
	else {
		return lhs.distance > rhs.distance;
	}
}

int dis[1010]; //存储节点当前距离起点的最小距离
int cost1[1010];
bool isVisited[1010]; //因为是无向图，为了避免造成回路，因此需要设置一个查看是否访问过的数组 
vector<Edge> graph[1010];

void Dijkstra(int s) {
	//1、先创建一个优先队列，用来保存下一个将要访问节点。存储什么？——内部储存结点的编号和距离，以及本题的花费
	priority_queue<PQNode> pqueue;  //这个队列会放当前符合条件最小的结点，所以如果要返回下一个节点，直接出队即可

	//2、设置一个距离表格并不断更新 （本题需要多设置一个花费表格） 
	for (int i = 0; i < 1010; ++i) {
		dis[i] = -1;  // -1在这里代表正无穷，刚开始都设置成正无穷
		cost1[i] = -1;
		isVisited[i] = false;  //所有节点都没有访问过  
	}

	//3、起点放进队列 
	dis[s] = 0;  //起点的距离先设置为0
	cost1[s] = 0; //起点的花费也为0
	PQNode qnode(s, 0, 0);
	pqueue.push(qnode);  //将起点压入队列

	//4、开始循环遍历查找
	while (!pqueue.empty()) {
		PQNode current = pqueue.top();
		int u = current.u;
		pqueue.pop();  //找出最小节点并出队 
		if (isVisited[u]) {  //之前已经访问过这个结点了，跳过找下一个 
			continue;
		}
		else {
			isVisited[u] = true;
			for (int i = 0; i < graph[u].size(); ++i) {  //遍历查找u这一行的邻接表 
				int v = graph[u][i].v;
				int weight = graph[u][i].weight;
				int cost = graph[u][i].cost;
				if (dis[v] == -1 ||
					dis[v] > dis[u] + weight ||
					dis[v] == dis[u] + weight && cost1[v] > cost1[u] + cost) {
					//①从v到原点之前是正无穷、
					//②更新前的路径比更新后的路径大
					//③更新前后路径相同，但花费更小   满足这三种情况，直接更新就行了 
					dis[v] = dis[u] + weight;
					cost1[v] = cost1[u] + cost;
					PQNode next(v, dis[v], cost1[v]); //更新完的邻居结点压回队列 
					pqueue.push(next);
				}
			}
		}
	}
	return;
}

int main() {
	int n, m;
	while (scanf("%d%d", &n, &m) != EOF) {
		if (n == 0 && m == 0) {
			break;
		}
		for (int i = 0; i < n; ++i) {   //初始化图 
			graph[i].clear();
		}

		for (int i = 0; i < m; ++i) {  //构建邻接表 
			int u, v, weight, cost;
			scanf("%d%d%d%d", &u, &v, &weight, &cost);
			//初始化邻接表，因为是无向图，所以两个起点又互为对方的终点 
			Edge e1(u, v, weight, cost);
			graph[u].push_back(e1);
			Edge e2(v, u, weight, cost);
			graph[v].push_back(e2);
		}
		int s, t; //需要查找的起点和终点
		scanf("%d%d", &s, &t);
		Dijkstra(s);
		printf("%d %d\n", dis[t], cost1[t]);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int MAX=1001;
const int INF=INT_MAX;

struct Edge{
	int to;
	int length;
	int cost;
	Edge(int t,int l,int c):to(t),length(l),cost(c){
	}
}; 

struct Point{
	int number;
	int distance;
	Point(int n,int d):number(n),distance(d){
	}
	bool operator< (const Point& p) const{
		return distance>p.distance;
	}
};

vector<Edge> graph[MAX];
int dis[MAX];
int price[MAX];

void Dijkstra(int s){
	priority_queue<Point> qu;
	dis[s]=0;
	price[s]=0;
	qu.push(Point(s,dis[s]));
	while(!qu.empty()){
		int u=qu.top().number;
		qu.pop();
		for(int i=0;i<graph[u].size();i++){
			int v=graph[u][i].to;
			int d=graph[u][i].length;
			int p=graph[u][i].cost;
			if(dis[v]>dis[u]+d||dis[v]==dis[u]+d&&price[v]>price[u]+p){
				dis[v]=dis[u]+d;
				price[v]=price[u]+p;
				qu.push(Point(v,dis[v]));
			}
		}
	}
	return ;
}

int main(){
	int n,m;
	while(cin>>n>>m){
		if(n==0&&m==0){
			break;
		}
		memset(graph,0,sizeof(graph));
		fill(dis,dis+n+1,INF);
		fill(price,price+n+1,INF);
		
		while(m--){
			int from,to,length,cost;
			cin>>from>>to>>length>>cost;
			graph[from].push_back(Edge(to,length,cost));
			graph[to].push_back(Edge(from,length,cost));
		}
		int s,t;
		cin>>s>>t;
		Dijkstra(s);
		cout<<dis[t]<<" "<<price[t]<<endl;
	}
	
}

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;
const int INF = INT_MAX;
const int MAX = 1001;    //村庄最大值
int dis[MAX];   //记录源点到各点的距离
int cost[MAX];  //记录花费
struct Point{
   int number;     //在邻接表内的下标
   int distance;  //该点距离源点的距离，用于优先队列排序
   Point (int a, int b): number(a), distance(b) {}
   bool operator< (const Point a) const {
       return distance > a.distance;   //test
   }
};
struct Edge{
   int to;
   int length;     //边长即距离
   int val;    //花费
   Edge (int a, int b, int c): to(a), length(b), val(c){}
};
vector<Edge> graph[MAX];

void Dijkstra(int s){       //输入起点
   priority_queue<Point> myqueue;
   myqueue.push(Point(s, 0));
   dis[s] = 0;
   cost[s] = 0;
   while(!myqueue.empty()){
       int u = myqueue.top().number;   //距离源点距离最短的点
       myqueue.pop();
       for(int i=0; i<graph[u].size(); ++i){   //以此点为中介
           int v = graph[u][i].to;     //u点邻接的点
           int d = graph[u][i].length;
           int c = graph[u][i].val;
           if(dis[u]+d < dis[v] || dis[u]+d == dis[v] && cost[u]+c < cost[v]){
               dis[v] = dis[u]+d;     //更新各点距离源点的距离
               cost[v] = cost[u]+c;
               myqueue.push(Point(v, dis[v]));     //小于则压
           }
       }
   }
   return;
}

int main(){
   int n, m;
   while(cin >> n >> m){
       if(n==0 && m==0) break;
       memset(graph, 0, sizeof(graph));    //向量初始化，清除上一轮数据
       fill(dis, dis+n+1, INF);
       fill(cost, cost+n+1, INF);  //从1开始
       int from, to, len, v, s, t;
       for(int i=0; i<m; ++i){
           cin >> from >> to >> len >> v;
           graph[from].push_back(Edge(to, len, v));
           graph[to].push_back(Edge(from, len, v));   //输入邻接表
       }
       cin >> s >> t;
       Dijkstra(s);
       cout << dis[t] << ' ' << cost[t] << endl;
   }
}