11565: 【原1565】最短路径问题

题目

题目描述

author: 孙梦璇原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1565

Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input Format

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。

(1<n<=1000, 0<m<100000, s != t)

Output Format

一行有两个数，最短距离及其花费。

Sample Input

Sample Output

9 11

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/17.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

constexpr int INF = 0x7fffffff;

int height[1001][1001];
int cost[1001][1001];

int minDist, minCost;

void dijkstra(int V, int start, int end) {
    int *distTo = new int[V + 1];
    int *costTo = new int[V + 1];
    bool *marked = new bool[V + 1]{};
    for (int i = 1; i <= V; ++i) {
        distTo[i] = height[start][i];
        costTo[i] = cost[start][i];
    }
    marked[start] = true;
    for (int i = 1; i <= V && !marked[end]; ++i) {
        int minDist = INF, v;
        for (int j = 1; j <= V; ++j) {
            if (marked[j] || minDist < distTo[j]) continue;
            minDist = distTo[j];
            v = j;
        }
        marked[v] = true;

        relax:
        for (int j = 1; j <= V; ++j) {
            if (marked[j] || height[v][j] == INF) continue;
            int newDist = distTo[v] + height[v][j];
            int newCost = costTo[v] + cost[v][j];
            if (distTo[j] > newDist) {
                distTo[j] = newDist;
                costTo[j] = newCost;
            } else if (distTo[j] == newDist) {
                if (costTo[j] > newCost)
                    costTo[j] = newCost;
            }
        }
    }
    minDist = distTo[end];
    minCost = costTo[end];
    delete[] distTo, costTo, marked;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, E;
    cin >> V >> E;
    for (int i = 1; i <= V; ++i) {
        for (int j = 1; j <= V; ++j) {
            if (i != j)
                height[i][j] = cost[i][j] = INF;
        }
    }

    int t1, t2, t3, t4;
    for (int i = 0; i < E; ++i) {
        cin >> t1 >> t2 >> t3 >> t4;
        if (height[t1][t2] > t3) {
            height[t1][t2] = height[t2][t1] = t3;
            cost[t1][t2] = cost[t2][t1] = t4;
        } else if (height[t1][t2] == t3 && cost[t1][t2] > t4) {
            cost[t1][t2] = cost[t2][t1] = t4;
        }
    }

    int s, t;
    cin >> s >> t;
    dijkstra(V, s, t);
    cout << minDist << ' ' << minCost << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

constexpr int max_size = 2000009;

class edge {
public:
    int to = 0;
    long long val = 0;
    long long money = 0;
    edge* next = nullptr;
};

edge* head[1009], * rear[1009];
int queue_data[max_size] = { 0 };
int queue_start = 0, queue_size = 0;

long long dis[1009] = { 0 }, cost[1009] = { 0 };

void SPFA(int from) {
    queue_data[(queue_start + queue_size) % max_size] = from;
    dis[from] = 0;
    cost[from] = 0;
    ++queue_size;
    while (queue_size) {
        auto temp = queue_data[queue_start % max_size];
        ++queue_start;
        --queue_size;
        for (auto p = head[temp]->next; p; p = p->next) {
            if (dis[temp] + p->val < dis[p->to]||
                (dis[temp] + p->val == dis[p->to] && cost[temp] + p->money < cost[p->to])) {
                dis[p->to] = dis[temp] + p->val;
                cost[p->to] = cost[temp] + p->money;
                queue_data[(queue_start + queue_size) % max_size] = p->to;
                ++queue_size;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= 1000; ++i) {
        rear[i] = head[i] = new edge;
        dis[i] = 999999999999;
        cost[i] = 999999999999;
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long c, money;
        cin >> u >> v >> c >> money;
        rear[u]->next = new edge;
        rear[u] = rear[u]->next;
        rear[u]->to = v;
        rear[u]->val = c;
        rear[u]->money = money;

        rear[v]->next = new edge;
        rear[v] = rear[v]->next;
        rear[v]->to = u;
        rear[v]->val = c;
        rear[v]->money = money;
    }

    int s, t;
    cin >> s >> t;

    SPFA(s);
    cout << dis[t] << " " << cost[t];

    return 0;
}