dijkstra堆优化模板 收藏方便找到该网站

欧清辣哨

#include<bits/stdc++.h>using namespace std;int xx,yy,vv,dis[510],len=0,lin[510],T,n,m;bool vis[510];struct one{    int y,v,next;};one e[20100];//priority_queue < pair < int , int > , vector<int> , greater<int> > q;priority_queue < pair < int , int > > q;void insert(){    e[++len].y=yy;e[len].v=vv;    e[len].next=lin[xx];lin[xx]=len;}int main(){    //freopen("xf.in","r",stdin);    //freopen("xf.out","w",stdout);    scanf("%d%d%d",&T,&n,&m);    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&xx,&yy,&vv);        insert();swap(xx,yy);insert();    }    memset(vis,false,sizeof(vis));    memset(dis,0x3f,sizeof(dis));    dis[1]=0;    q.push(make_pair(0,1));    while(q.size())    {        int x=q.top().second;q.pop();        if(vis[x])continue;         vis[x]=true;        for(int i=lin[x];i;i=e.next)        {            if(dis[e.y]>dis[x]+e.v)            {                dis[e.y]=dis[x]+e.v;                q.push(make_pair(-dis[e.y],e.y));            }        }    }    int sum=0;    for(int i=1;i<=n;i++)printf("%d\n",dis);    return 0;}/*#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<iomanip>#include<cmath>using namespace std;int t,f,p,x[510][510],dis[11000],vis[11000],sum=0;void dijkstra(int st){    for(int i=1;i<=f;i++) dis=x[st];    memset(vis,0,sizeof(vis));    vis[st]=1;dis[st]=0;    for(int i=2;i<=f;i++)    {        int minn=999999999;        int k=0;        for(int j=1;j<=f;j++)            if(vis[j]==0&&dis[j]<minn)            {                minn=dis[j];                k=j;            }            if(k==0) return;            vis[k]=1;            for(int j=1;j<=f;j++)            {                if(vis[j]==0&&dis[k]+x[k][j]<dis[j])                {                    dis[j]=dis[k]+x[k][j];                }            }    }    }int main(){    memset(dis,9,sizeof(dis));    memset(x,9,sizeof(x));    scanf("%d%d%d",&t,&f,&p);    for(int i=1;i<=p;i++)    {        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        if(x[a]>c)        {        x[a]=c;        x[a]=c;        }    }    dijkstra(1);    for(int i=1;i<=f;i++)        if(dis<=t) sum++;    cout<<sum<<endl;    return 0;}*/ 有相同爱好的可以进来一起讨论哦：企鹅群号：1046795523

学习视频资料：http://www.makeru.com.cn/live/1392_1164.html?s=143793