链式前向星求助
查看原帖
链式前向星求助
206423
焚魂楼主2021/8/21 10:18

用链式前向星就只有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;
}
2021/8/21 10:18
加载中...