11635: 【原1635】经济出行计划
题目
题目描述
author: Spy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1635
Description
暑假就要到啦,不知道大家都打算去哪里玩呢~
出行之前,规划行程是个幸福又痛苦的过程,因为这需要解决有限的时间、金钱与无限可能的体验之间的冲突。
解决复杂问题先从简单的单因素情况出发,你所在的世界有n个城市(编号为1~n,1为出发城市,n为目的城市),一些城市之间可以互相来往,来往的交通方式是以下三者之一:海运、铁路、空运,这三种出行方式的费用分别为1,2,3。
现在只考虑费用,请你找到最经济的出行方式。
Input Format
第一行有两个整数\(N,M\) ,代表城市数量和城市之间的路径数量。
接下来 \(M\) 行,每行3个整数 \(u,v,c\),代表城市\(u\)和\(v\)之间的交通方式费用为\(c\)。
Output Format
输出一行代表最小费用。
Sample Input
4 4
1 2 3
1 3 2
2 4 1
3 4 3
Sample Output
4
Limits
对于\(30\%\)的数据,c = 1
对于\(50\%\)的数据,\(N,M < 10^{3}\)
对于\(100\%\)的数据,\(N,M < 10^{6}\)
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;
edge* next = nullptr;
};
edge* head[1000009], *rear[1000009];
int queue_data[max_size] = { 0 };
int queue_start = 0, queue_size = 0;
long long dis[1000009] = { 0 };
void SPFA(int from) {
queue_data[(queue_start + queue_size) % max_size] = from;
dis[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[p->to] = dis[temp] + p->val;
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 <= n; ++i) {
rear[i] = head[i] = new edge;
dis[i] = 999999999999;
}
for (int i = 0; i < m; ++i) {
int u, v;
long long c;
cin >> u >> v >> c;
rear[u]->next = new edge;
rear[u] = rear[u]->next;
rear[u]->to = v;
rear[u]->val = c;
rear[v]->next = new edge;
rear[v] = rear[v]->next;
rear[v]->to = u;
rear[v]->val = c;
}
SPFA(1);
cout << dis[n];
return 0;
}
zqy2018's solution
/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1635.md
*/
#include <cstdio>
#include <cstring>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, m;
int to2[2000005], nxt2[2000005], at2[3000005] = {0}, cnt2 = 0;
int to[2000005], nxt[2000005], at[1000005] = {0}, w[2000005], cnt = 0;
int dis[1000005];
void init(){
n = read(), m = read();
for (int i = 1; i <= m; ++i){
int u = read(), v = read(), ww = read();
to[++cnt] = v, w[cnt] = ww, nxt[cnt] = at[u], at[u] = cnt;
to[++cnt] = u, w[cnt] = ww, nxt[cnt] = at[v], at[v] = cnt;
}
}
void solve(){
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
to2[++cnt2] = 1, nxt2[cnt2] = at2[0], at2[0] = cnt2;
int cur = 0;
for (int i = 1; i <= n; ++i){
while (!at2[cur]) ++cur;
for (int j = at2[cur]; j; j = nxt2[j]){
int u = to2[j];
if (dis[u] < cur) continue;
for (int t = at[u]; t; t = nxt[t]){
int v = to[t];
if (dis[v] <= dis[u] + w[t]) continue;
dis[v] = dis[u] + w[t];
to2[++cnt2] = v, nxt2[cnt2] = at2[dis[v]], at2[dis[v]] = cnt2;
}
}
++cur;
}
printf("%d\n", dis[n]);
}
int main(){
init();
solve();
return 0;
}