最短路径问题

//首先这个题目按照题意是不能用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 <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;
}

#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;
}

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;
}

#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;
   }
}

#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1001;
const int INF = INT_MAX;    //无穷设为很大的数

struct Edge {
    int to;     //终点
    int length; //长度
    int price;  //花费
    Edge(int to, int length, int price): to(to), length(length), price(price) {}
};

struct Point {
    int number;     //点的编号
    int distance;   //源点到该点距离
    Point(int number, int distance): number(number), distance(distance) {}
    bool operator<(const Point& p)const {
        return distance > p.distance;       //距离小的优先级高
    }
};

vector<vector<Edge>>graph(MAXN);    //邻接表实现的图
vector<int>dis(MAXN);               //源点到各点距离
vector<int>cost(MAXN);              //源点到各点花费

void Dijkstra(int s) {  //迪杰斯特拉算法求最短路径，s为源点
    priority_queue<Point>myPriorityQueue;   //优先队列存放待处理点
    dis[s] = 0;
    cost[s] = 0;
    myPriorityQueue.push(Point(s, dis[s])); //源点入队
    while (!myPriorityQueue.empty()) {
        int u = myPriorityQueue.top().number;   //离源点最近的点
        myPriorityQueue.pop();
        for (auto& i : graph[u]) {  //遍历点u的邻接表
            int v = i.to;
            int l = i.length;
            int p = i.price;
            if ((dis[v] == dis[u] + l && cost[v] > cost[u] + p) ||
                    dis[v] > dis[u] + l) {  //松弛操作
                dis[v] = dis[u] + l;
                cost[v] = cost[u] + p;
                myPriorityQueue.push(Point(v, dis[v]));
            }
        }
    }
}

int main() {
    int n, m;
    while (cin >> n >> m && !(n == 0 && m == 0)) {
        fill(dis.begin(), dis.begin() + n + 1, INF);    //距离初始化为无穷
        fill(cost.begin(), cost.begin() + n + 1, INF);  //花费初始化为无穷
        while (m--) {
            int from, to, length, price;
            cin >> from >> to >> length >> price;
            graph[from].push_back(Edge(to, length, price));
            graph[to].push_back(Edge(from, length, price));
        }
        int s, t;       //起点与终点
        cin >> s >> t;
        Dijkstra(s);
        cout << dis[t] << " " << cost[t] << endl;
    }
    return 0;
}

真是吐了,算法没问题,总是结果不对,最后把正确答案的矩阵拿来对,发现是题目理解的问题,这本身
是个无向图,测试集里会有反复出现重复边,要选择最小的使用,假如不知道的话真的会莫名其妙卡
很久,我的DJ还是挺标准的复线的算法导论里的代码,但是EXTRACT-MIN没有用优先队列,因为似乎是
存在更新的问题没搞明白,但就算轮训找最小其实复杂度也没高多少.

#include <vector>
#include "queue"
#include "iostream"

using namespace std;

vector<vector<int>> graph;
vector<vector<int>> cost;

struct Vertex {
    int id;
    int key;
    int cost;
};

void RELAX(Vertex &u, Vertex &v) {
    if (graph[u.id][v.id] + u.key < v.key) {
        v.key = graph[u.id][v.id] + u.key;
        v.cost = u.cost + cost[u.id][v.id];
    }else if(graph[u.id][v.id] + u.key == v.key){
        if(v.cost > u.cost + cost[u.id][v.id]) v.cost = u.cost + cost[u.id][v.id];
    }
}

// 找到key最小的vertex
Vertex* ExtractMin(vector<Vertex *> &temp) {
    int min = 0;
    for (int i = 1; i < temp.size(); ++i) {
        if (temp[i]->key < temp[min]->key) {
            min = i;
        }
    }
    Vertex *res = temp[min];
    temp.erase(temp.begin() + min, temp.begin() + min + 1);
    return res;
}

void DJ(Vertex &s, vector<Vertex> &vec, vector<Vertex *> &priority) {
    s.key = 0;
    s.cost = 0;
    while (!priority.empty()) {
        Vertex *u = ExtractMin(priority);
        for (int i = 0; i < graph.size(); ++i) {
                RELAX(*u, vec[i]);
        }
    }
}


int main() {
    int n, m;
    while (cin >> n >> m) {
        if(n==0) continue;
        vector<Vertex> vec(n);
        vector<Vertex *> priority(n);

        // init
        for (int i = 0; i < n; ++i) {
            vec[i].id = i;
            vec[i].key = INT32_MAX;
            vec[i].cost = INT32_MAX;
            priority[i] = &vec[i];
        }

        // 记录信息
        graph.resize(n);
        cost.resize(n);
        for (int i = 0; i < n; ++i) {
            vector<int> row(n, INT32_MAX);
            vector<int> costRow(n, INT32_MAX);
            graph[i] = row;
            cost[i] = costRow;
        }



        // 输入信息
        for (int i = 0; i < m; ++i) {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            a--;
            b--;
            if(graph[a][b] > c){
                graph[a][b] = c;
                graph[b][a] = c;
                cost[a][b] = d;
                cost[b][a] = d;
            }
            if(graph[a][b] == c){
               if(cost[a][b] > d){
                   cost[a][b] = d;
                   cost[b][a] = d;
               }
            }


        }

        // 对角线化为0
//        for (int i = 0; i < n; ++i) {
//            graph[i][i] = 0;
//            cost[i][i] = 0;
//        }

        // 起点终点
        int start, end;
        cin >> start >> end;
        DJ(vec[start-1], vec, priority);

//        for (int i = 0; i < graph.size(); ++i) {
//            for (int j = 0; j < graph.size(); ++j) {
//                cout << graph[i][j] <<" ";
//            }
//            cout << endl;
//        }
//        cout << endl;
//        cout << endl;
//        for (int i = 0; i < graph.size(); ++i) {
//            for (int j = 0; j < graph.size(); ++j) {
//                cout << cost[i][j] <<" ";
//            }
//            cout << endl;
//        }
//        cout << endl;
//        cout << endl;

        for (int i = 0; i < vec.size(); ++i) {
//            cout << vec[i].key << " " << vec[i].cost << endl;
        }
        cout << vec[end-1].key <<" " << vec[end-1].cost << endl;
    }
}