最短路径问题

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1010;
const int INF = 1e9;

struct Node{
    int v, dis, co;
    Node(int _v, int _dis, int _co) : v(_v) , dis(_dis), co(_co) {}
    bool friend operator < (Node n1, Node n2){//设置优先级，即距离短的优先级高
        return n1.dis > n2.dis;
    }
};

vector<Node> Adj[MAXV];
priority_queue<Node> q;//优先队列大法

int n, m, s;//顶点数、边数、起点下标
int dis[MAXV];
int cost[MAXV];
bool vis[MAXV] = {false};

void init(int n){
    fill(dis, dis + n + 1, INF);
    fill(cost, cost + n + 1, INF);
    fill(vis, vis + n + 1, false);
    for(int i = 1; i <= n; ++i){
        Adj[i].clear();
    }
}

void Dij(int s){
    dis[s] = 0, cost[s] = 0;
    q.push(Node(s, 0, 0));//放入起点
    //求出使d[u]最小的还未被访问的顶点的编号
    while(!q.empty()){
        Node t = q.top();
        q.pop();
        int u = t.v;
        if(vis[u]) continue; 
        vis[u] = true;

        for(int j = 0; j < Adj[u].size(); ++j){
            int v = Adj[u][j].v;
            if(!vis[v] && Adj[u][j].dis + dis[u] < dis[v] || 
                Adj[u][j].dis + dis[u] == dis[v] && Adj[u][j].co + cost[u] < cost[v]){
                dis[v] = Adj[u][j].dis + dis[u];
                cost[v] = Adj[u][j].co + cost[u];
                q.push(Node(v, dis[v], cost[v]));
            }
        }
    }
}
int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int a, b, d, p, s, t;
    while(~scanf("%d %d", &n, &m) && n){
        init(n);
        //顶点个数、边数、起点编号
        while(m--){
            scanf("%d %d %d %d", &a, &b, &d, &p);
            Adj[a].push_back(Node(b, d, p));
            Adj[b].push_back(Node(a, d, p)); 
        }
        scanf("%d %d", &s, &t);
        Dij(s);//Dijkstra算法入口
        printf("%d %d\n", dis[t], cost[t]);
    }
    return 0;
}