用链式前向星就只有10pts但是邻接矩阵就能AC是什么鬼QAQ
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,s,t;
int x,y,w;
struct node{
int next,to,w;
}eage[10010];
int head[10010];
bool v[10010];
int dis[10010];
int map[2510][2510];
int cnt = 1;
void add(int u,int v,int w) {
eage[cnt].to = v;
eage[cnt].w = w;
eage[cnt].next = head[u];
head[u] = cnt++;
}
void dijskstra() {
dis[s] = 0;
for(int i = 1;i <= n;i++) {
int k = 0;
for(int j = 1;j <= n;j++) {
if(!v[j] && dis[j] < dis[k])
k = j;
}
v[k] = true;
for(int j = head[k];j != -1;j = eage[j].next) {
if(!v[eage[j].to] && dis[k] + eage[j].w < dis[eage[j].to])
dis[eage[j].to] = dis[k] + eage[j].w;
}
// for(int j = 1;j <= n;j++) {
// if(!v[j] && dis[k] + map[k][j] < dis[j])
// dis[j] = dis[k] + map[k][j];
// }
}
}
int main() {
cin >> n >> m >> s >> t;
memset(head,-1,sizeof(head));
memset(eage,-1,sizeof(eage));
memset(dis,127/3,sizeof(dis));
// memset(map,127/3,sizeof(map));
for(int i = 1;i <= m;i++) {
cin >> x >> y >> w;
// map[x][y] = w;
// map[y][x] = w;
add(x,y,w);
add(y,x,w);
}
dijskstra();
cout << dis[t];
return 0;
}