139. 旅游规划

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001;
const int INF=0x3f3fLL;
typedef struct _graph{
    int vertix;
    int edge;
    int martix[maxn][maxn];
    int number[maxn][maxn];
}Graph,*PGraph;
void Dijkstra(int disc[],int get[],int via,Graph G)
{
    bool visited[maxn];int sum=G.vertix;
    memset(disc,INF,sizeof(disc));
    memset(visited,false,sizeof(visited));
    memset(get,INF,sizeof(get));
    disc[via]=0,visited[via]=true;sum--;
    get[via]=0;
    for(int i=0;i<G.vertix;i++){
        if(G.martix[via][i]!=INF){
            disc[i]=G.martix[via][i];
            get[i]=G.number[via][i];
        }
    }
    while(sum){
        int mind=INF+10,k=0,coin=INF; 
        for(int i=0;i<G.vertix;i++){
            if(visited[i]==false){
                if(disc[i]<=mind){
                   mind=disc[i];
                   k=i;coin=get[i];
                }
            }
        }
        visited[k]=true;
        for(int i=0;i<G.vertix;i++){
            if(visited[i]==false){
                if(G.martix[k][i]!=INF){
                    if(disc[i]>G.martix[k][i]+disc[k]){
                        disc[i]=G.martix[k][i]+disc[k];
                        get[i]=get[k]+G.number[k][i];
                    }
                    else if(disc[i]==G.martix[k][i]+disc[k]){
                        if(get[i]>=get[k]+G.number[k][i]) get[i]=get[k]+G.number[k][i];
                    }
                }
            }
        }
        sum--;
    }
}
int main()
{
    int n,m,s,d;cin>>n>>m>>s>>d;
    Graph G;int disc[n+10],get[n+10];
    G.vertix=n,G.edge=m;
    memset(G.martix,INF,sizeof(G.martix));
    memset(G.number,0,sizeof(G.number));
    while(m--){
        int a,b,c,d;cin>>a>>b>>c>>d;
        G.martix[a][b]=c,G.martix[b][a]=c;
        G.number[a][b]=d,G.number[b][a]=d;
    }
    Dijkstra(disc,get,s,G);
    cout<<disc[d]<<" "<<get[d]<<endl;
}

#include <bits/stdc++.h>

using namespace std;

struct Node {
    Node() = default;
    Node(int id, int dist) : id(id), dist(dist) {}
    bool operator<(const Node& node) const {
        return dist > node.dist;
    }

    int id, dist;
};

int main() {
    constexpr int inf = numeric_limits<int>::max() / 2;

    int N, M, S, D;
    cin >> N >> M >> S >> D;
    vector<vector<int>> graph(N, vector<int>(N, inf)), cost(N, vector<int>(N, inf));

    while (M--) {
        int s, e, l, c;
        cin >> s >> e >> l >> c;
        graph[s][e] = graph[e][s] = l, cost[s][e] = cost[e][s] = c;
    }

    for (int i = 0; i < N; ++i) {
        graph[i][i] = 0, cost[i][i] = 0;
    }

    vector<int> d(N, inf), c(N, inf), visited(N);
    d[S] = 0, c[S] = 0;

    priority_queue<Node> queue;
    queue.push({ S,0 });
    while (!queue.empty()) {
        auto node = queue.top();
        queue.pop();

        visited[node.id] = 1;

        for (int i = 0; i < N; ++i) {
            if (!visited[i]) {
                if (node.dist + graph[node.id][i] < d[i]) {
                    d[i] = node.dist + graph[node.id][i];
                    c[i] = c[node.id] + cost[node.id][i];
                    queue.push({ i,d[i] });
                }
                else if (node.dist + graph[node.id][i] == d[i]) {
                    c[i] = min(c[i], c[node.id] + cost[node.id][i]);
                }
            }
        }
    }

    printf("%d %d\n", d[D], c[D]);
}