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

题目描述

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

Input Format

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

Sample Input

``````3 2
1 2 5 6
2 3 4 5
1 3
``````

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

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