最短路入门题-白红宇

最短路入门题

阅读量：5813 次

发布时间：2019-06-18

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

http://acm.hdu.edu.cn/showproblem.php?pid=2544

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 1000001using namespace std;int map[101][101];int n,m;int v[101],dis[101];void D(){
        memset(v,0,sizeof(v));    for(int i=1;i<=n;i++)        dis[i]=map[1][i];    dis[1]=0;    v[1]=1;    int min,k;    for(int i=1;i
         
          dis[j]) { min=dis[j]; k=j; } } v[k]=1; for(int j=1;j<=n;j++) { if(!v[j]&&map[k][j]+dis[k]
          
           z) { map[x][y]=z; map[y][x]=z; } } D(); } return 0;} BE

#include 
    
     #include 
     
      #include 
      
       #define N 1000001int n,m,flag,t;struct node{
        int x,y,w;}edge[20002];int dis[101];void add(int x,int y,int w){
        edge[t].x=x;    edge[t].y=y;    edge[t++].w=w;}void B(){
        for(int i=1;i<=n;i++)        dis[i]=N;    dis[1]=0;    for(int i=1;i

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 1000001using namespace std;int map[101][101];int n,m;void F(){
        for(int k=1;k<=n;k++)    {
            for(int i=1;i<=n;i++)        {
                for(int j=1;j<=n;j++)            {
                    if(map[i][k]+map[k][j]
         
          z) { map[x][y]=z; map[y][x]=z; } } F(); printf("%d\n",map[1][n]); } return 0;}

 SPFA

#include 
    
     #include 
     
      #include 
      
       #define N 1000001int n,m;struct node{
        int x,y,z,next;}edge[20004];int head[102];int dis[102];int v[102];int t;void init(){
        memset(head,-1,sizeof(head));    t=0;}void add(int x,int y,int z){
        edge[t].x=x;    edge[t].y=y;    edge[t].z=z;    edge[t].next=head[x];    head[x]=t++;}int q[20004];void SPFA(){
        memset(v,0,sizeof(v));    for(int i=1;i<=n;i++)        dis[i]=N;    dis[1]=0;    int e=0;    int s=0;    int tt;    q[e++]=1;    v[1]=1;    while(s
       
        dis[q[s]])                    q[e++]=edge[i].y;                  //  else q[--s]=edge[i].y;                    v[edge[i].y]=1;                }            }        }    }    printf("%d\n",dis[n]);}int main(){
        int x,y,z;    while(scanf("%d%d",&n,&m)!=EOF&&(m||n))    {
            init();        while(m--)        {
                scanf("%d%d%d",&x,&y,&z);            add(x,y,z);            add(y,x,z);        }        SPFA();    }}