1129. 热浪【单源最短路板子题】

https://www.acwing.com/problem/content/1131/
朴素版Dijkstra()

#include
using namespace std;
const int N=2510;
int g[N][N],st[N],n,t,startx,endx;
int dist[N];
void Dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[startx]=0;
    for(int i=0;i>n>>t>>startx>>endx;
    for(int i=0;i>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    Dijkstra();
    cout< 
堆优化版的Dijkstra()
 
#include
using namespace std;
const int N=1e5*2+10;
typedef pair PII;
int h[N],e[N],w[N],ne[N],idx;
int n,t,startx,endx;
int st[N],dist[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void Dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[startx]=0;
    priority_queue,greater> heap; heap.push({0,startx});
    while(heap.size())
    {
        auto t=heap.top(); heap.pop();
        int u=t.second,d=t.first;
        if(st[u]) continue;
        st[u]=1;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>d+w[i])
            {
                dist[j]=d+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}
int main(void)
{
    cin>>n>>t>>startx>>endx;
    memset(h,-1,sizeof h);
    while(t--)
    {
        int a,b,c; cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    Dijkstra();
    cout< 
spfa()
 
#include
using namespace std;
const int N=1e5*2+10;
int h[N],e[N],w[N],ne[N],idx;
int n,t,startx,endx;
int dist[N],st[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[startx]=0; st[startx]=1;
    queueq; q.push(startx);
    while(q.size())
    {
        int u=q.front(); q.pop();
        st[u]=0;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[u]+w[i])
            {
                dist[j]=dist[u]+w[i];
                if(!st[j]) q.push(j),st[j];
            }
        }
    }
}
int main(void)
{
    memset(h,-1,sizeof h);
    cin>>n>>t>>startx>>endx;
    while(t--)
    {
        int a,b,c; cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    spfa();
    cout<