Skip to content

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