### 扎心了老铁
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2500, MAXM = 200000, INF = 2147483647;
int head[MAXN + 10], n, m, cnt, d[MAXN + 10];
queue <int> nod;
bool visit[MAXN + 1];
struct EDGE{
int next, to, w;
};
EDGE edge[MAXM + 10];
inline int read(){
char ch = getchar();
int f = 1, x = 0;
while(!isdigit(ch)){
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)){
x *= 10;
x += (ch & 15);
ch = getchar();
}
return f * x;
}
void add(int from, int to, int v){
edge[++cnt].next = head[from];
edge[cnt].to = to;
edge[cnt].w = v;
head[from] = cnt;
}
void spfa(int x){
fill(d + 1, d + n + 1, INF); d[x] = 0;
nod.push(x); visit[x] = 1;
while(nod.size()){
int k = nod.front(); nod.pop(); visit[k] = 0;
for(int i = head[k]; i != 0; i = edge[i].next){
int j = edge[i].to;
if(d[j] > d[k] + edge[i].w){
d[j] = d[k] + edge[i].w;
if(!visit[j]){
nod.push(j);
visit[j] = 1;
}
}
}
}
return;
}
int main(){
n = read(); m = read();
for(int i = 1; i <= m; i++){
int a, b, c;
a = read(); b = read(); c = read();
add(a, b, c); add(b, a, c);
}
spfa(1);
printf("%d\n",d[n]);
return 0;
}
```
#### RE 80
by Ireliaღ @ 2018-11-17 11:13:12
@[做梦都想AK](/space/show?uid=101528)
我又试了一下，边有重的，存边数组开的比数据大点就OK了，我把MAXM加俩零过了
by Ireliaღ @ 2018-11-17 11:16:22