T了1,5为啥

longerfu @ 2024-04-11 22:06:21

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node{
    int w,to,nxt;
}edge[500010];
int dict[500010];
priority_queue<int>q;
bool vis[500010];
int head[500010];
int cnt;
int n,m,s;
void _add(int u,int v,int w)
{   
    cnt++;
    edge[cnt].w = w;
    edge[cnt].to = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        _add(u,v,w);        
    }
    for(int i=1;i<=n;i++) dict[i]=2147483647;
    dict[s] = 0;
    vis[s] = 1;
    q.push(s);
    while(!q.empty())
    {
        int u = q.top();
        q.pop();
        vis[u] = 0;
        for(int i = head[u];i;i=edge[i].nxt)
        {
            int v = edge[i].to;
        //  if(vis[v]) continue;
            if(dict[u]+edge[i].w < dict[v])
            {
                dict[v] = dict[u]+edge[i].w;
                if(vis[v]==0)
                {
                    vis[v] = 1;
                    q.push(v);  
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        cout<<dict[i]<<" ";  
    }
    return 0;
}

by ___A__ @ 2024-04-11 22:07:40

因为卡了spfa 你需要玄学优化

by longerfu @ 2024-04-11 22:09:20

@_A 咋优化啊 我卡了一天了

by longerfu @ 2024-04-11 22:10:14

@_A vis=1 continue 只能过2个点

by longerfu @ 2024-04-11 22:15:43

@_A ok

by ___A__ @ 2024-04-11 22:17:09

@longerfu 比如这样就行

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node{
    int w,to,nxt;
}edge[500010];
int dict[500010];
struct cmp{
    int operator()(int x,int y){
        return dict[x]>dict[y];
    }
};
priority_queue<int,vector<int>,cmp>q;
bool vis[500010];
int head[500010];
int cnt;
int n,m,s;
void _add(int u,int v,int w)
{   
    cnt++;
    edge[cnt].w = w;
    edge[cnt].to = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        _add(u,v,w);        
    }
    for(int i=1;i<=n;i++) dict[i]=2147483647;
    dict[s] = 0;
    vis[s] = 1;
    q.push(s);
    while(!q.empty())
    {
        int u = q.top();
        q.pop();
        vis[u] = 0;
        for(int i = head[u];i;i=edge[i].nxt)
        {
            int v = edge[i].to;
        //  if(vis[v]) continue;
            if(dict[u]+edge[i].w < dict[v])
            {
                dict[v] = dict[u]+edge[i].w;
                if(vis[v]==0)
                {
                    vis[v] = 1;
                    q.push(v);  
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        cout<<dict[i]<<" ";  
    }
    return 0;
}