最短路径---dijkstra算法模板

dijkstra算法模板

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

 #include<stdio.h>

 #include<string.h>

 #include<math.h>

 #include<iostream>

 #include<stdlib.h>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<string>

 #include<set>

 #include<cctype>

 #include<sstream>

 #define mem(a) memset(a,0,sizeof(a))

 #define LL long long

 #define inf 0x3f3f3f3f

 using namespace std;

 const int N=1e3+;

 int mp[N][N],dis[N],mark[N];

 int n,m;

 int dijkstra(int s,int t)

 {

    for(int i=;i<n;i++)

    dis[i]=(i==s?:mp[s][i]);

    mark[s]=;

    //dis[s]=0;

    int v;

    for(int i=;i<n;i++)

    {

       int mx=inf;

       for(int j=;j<n;j++)

         if(dis[j]<mx&&!mark[j])

           mx=dis[v=j]; //%%%

       if(mx==inf) break;

       mark[v]=;

       for(int j=;j<n;j++)

       {

           if(!mark[j]&&(dis[j]>dis[v]+mp[v][j]))

             dis[j]=dis[v]+mp[v][j];

       }

    }

    if(dis[t]>=inf) return -;

    return dis[t];

 }

 int main()

 {

  while(~scanf("%d%d",&n,&m)&&(n+m))

  {

      for(int i=;i<n;i++)

      {

        for(int j=;j<n;j++)

        {

            if(i==j)mp[i][j]=;

            else mp[i][j]=inf;

        }

      }

      mem(mark);

      int l,r,x;

      for(int i=;i<=m;i++)

      {

          scanf("%d%d%d",&l,&r,&x);

          if(mp[l][r]>x) mp[l][r]=mp[r][l]=x;

      }

      int s,t;

      scanf("%d%d",&s,&t);

      printf("%d\n",dijkstra(s,t));

  }

  return ;

 }