最短路模板题，有一个坑，用dijkstra算法时两点之间可能有多条路，要存取最短的那条。

dijkstra:

#include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x3f3f3fusing namespace std;int a[1005][1005];int dis[1005],vis[1005];int main(){    int n,t;    scanf("%d%d",&t,&n);    memset(vis,0,sizeof(vis));    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)    {        if(i==j) a[i][j]=0;        else a[i][j]=inf;    }    while(t--)    {        int x,y,c;        scanf("%d%d%d",&x,&y,&c);         a[x][y]=a[y][x]=min(a[x][y],c);    }    for(int i=1;i<=n;i++)        dis[i]=a[1][i];        vis[1]=1;    for(int i=1;i
         
          dis[u]+a[u][k])                    dis[k]=dis[u]+a[u][k];        }    }    printf("%d\n",dis[n]);    return 0;}
         
        
       
      
     

Bellman-Ford:要考虑路是双向的

#include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x3f3f3fusing namespace std;int u[2005],v[2005],c[2005];int dis[1005];int n,t;int main(){    scanf("%d%d",&t,&n);    memset(dis,inf,sizeof(dis));    for(int i=1; i<=t; i++)        scanf("%d%d%d",&u[i],&v[i],&c[i]);    dis[1]=0;    for(int i=1;i
         
          dis[u[j]]+c[j])                dis[v[j]]=dis[u[j]]+c[j];            if(dis[u[j]]>dis[v[j]]+c[j])            dis[u[j]]=dis[v[j]]+c[j];        }    printf("%d\n",dis[n]);    return 0;}