模板题，求调，玄关

chen_z @ 2023-10-19 13:41:46

#include<bits/stdc++.h>
#define inf 2147483647
using namespace std;
struct csq{
    int loc,num;
    friend bool operator <(csq a,csq b){a.num>b.num;};
};
struct node{int to,w;};
priority_queue<csq> q;
vector<node> e[100010];
int n,m,s,dis[100010],vis[100010]; 
void dijkstra(){
    for(int i=1;i<=n;i++)dis[i]=inf;
    dis[s]=0;
    q.push((csq){s,0});
    while(!q.empty()){
        int u=q.top().loc;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<e[u].size();i++){
            node t=e[u][i];
            if(dis[t.to]>dis[u]+t.w){
                dis[t.to]=dis[u]+t.w;
                if(!vis[t.to])q.push((csq){t.to,dis[t.to]});
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back((node){v,w});
    }
    dijkstra();
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
    return 0;
}

by chen_z @ 2023-10-19 13:42:18

能过样例，只AC倒数第二个点

by chen_z @ 2023-10-19 13:43:21

学废了，复习时发现模板不会了。。。。抽象，甚至这是一个红名

by FelixYeFei @ 2023-10-19 13:56:17

这是我写的，你可以参考一下：

#include <bits/stdc++.h>
using namespace std;
struct Edge
{
    long long v, w;
    bool operator<(const Edge& u)const
    {
        return w > u.w;
    }
};
vector<Edge> edge[100005];
int n, m;
long long dis[100005];
bool vis[100005];
priority_queue<Edge> q;
void digkstra(int s)
{
    for (int i = 1; i <= n; i++){dis[i] = 1e9;vis[i] = 0;}
    while(!q.empty()) q.pop();
    dis[s] = 0;q.push({s, 0});
    while(!q.empty())
    {
        int num = q.top().v;
        q.pop();
        if (vis[num]) continue;
        vis[num] = 1;
        for (int i = 0; i < edge[num].size(); i++)
        {
            if (!vis[edge[num][i].v] && dis[num] + edge[num][i].w < dis[edge[num][i].v])
            {
                dis[edge[num][i].v] = dis[num] + edge[num][i].w;
                q.push({edge[num][i].v, dis[edge[num][i].v]});
            }
        }
    }
}
int main()
{
    int s, u, v, w;
    scanf("%d%d%d",&n,&m,&s);   
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        Edge a;a.v = v;a.w = w;
        edge[u].push_back(a);
    }
    digkstra(s);
    for (int i = 1; i <= n; i++) printf("%lld ",dis[i]);
    return 0;
}

by FelixYeFei @ 2023-10-19 13:56:39

@chen_z

by tai_chi @ 2023-10-19 14:18:53

@chen_z 1. 重载运算符没有返回值

2. 似乎要开 long long

这两个加上就过了

by chen_z @ 2023-10-20 12:28:27

@New_Beginning 好的好的，谢谢啦！

by chen_z @ 2023-10-20 12:30:13

@FelixYeFei 谢谢，之前写过链式前向星的代码，对照着没找出来错

by chen_z @ 2023-10-20 12:34:40

@New_Beginning 我靠，wssb，压行把return压没了