# 11635: 【原1635】经济出行计划

### 题目描述

author: Spy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1635

# Description

## Sample Input

``````4 4
1 2 3
1 3 2
2 4 1
3 4 3
``````

## Sample Output

``````4
``````

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

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 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(){
for (int i = 1; i <= m; ++i){
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;
}
``````