P3371最短路-白红宇

P3371最短路

阅读量：6196 次

发布时间：2019-06-21

本文共 1512 字，大约阅读时间需要 5 分钟。

Dijkstra算法

#include
     
      #include
      
       #include
       
        #include
        
          #include
         
          #include
          
           int maxn=2147483647;int minn;using namespace std;struct H{ int to;//邻接点 int ll;//边权 };vector 
           
             w[10001];//动态数组int dis[10001];int f[10001];int main(){ int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++) { int x,y,l; scanf("%d%d%d",&x,&y,&l); H k; k.to=y; k.ll=l; w[x].push_back(k); } f[s]=1; for(int i=1;i<=n;i++)dis[i]=maxn; for(int i=0;i

spfa算法

#include
     
      #include
      
        #include
       
        #include
        
         #include
         
          #define LL long long#define mm 2147483647using namespace std;struct H{    int to;    int ll;};vector
          
            w[10001];//动态数组，节省空间int f[10001];int dis[10001];int team[10*10001];//要大，因为要入很多点int main(){ int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++) { int x,y,l; scanf("%d%d%d",&x,&y,&l); H p; p.to=y,p.ll=l; w[x].push_back(p); } for(int i=1;i<=n;i++)dis[i]=mm; dis[s]=0; //初始化 int head=0,tail=1; team[1]=s,f[s]=1; while(tail>head) { int k=team[++head]; f[k]=0;//出队 for(int i=0;i
           
            dis[k]+w[k][i].ll) { dis[w[k][i].to]=dis[k]+w[k][i].ll; if(!f[w[k][i].to])//队列中不存在w[k][i].to点 { team[++tail]=w[k][i].to;//入队 f[team[tail]]=1; } } } } for(int i=1;i<=n;i++) printf("%d ",dis[i]); //printf("%d",sizeof(w)/1024/1024); return 0;}