图结构练习——最短路径

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

 给定一个带权无向图，求节点1到节点n的最短路径。

 

输入

 输入包含多组数据，格式如下。

第一行包括两个整数n m，代表节点个数和边的个数。(n<=100)

剩下m行每行3个正整数a b c，代表节点a和节点b之间有一条边，权值为c。

 

输出

 每组输出占一行，仅输出从1到n的最短路径权值。（保证最短路径存在）

 

示例输入

3 21 2 11 3 11 0

示例输出

10

#include 
     
      #include 
      
       #include 
       
        #define inf 9999999int ma[110][110];//记录地图int dis[110];int vis[110];//标记int n,m;int s,e;//初始点和终点void dij(){    int i,j;    int pos;    s=1;    e=n;    memset(vis,0,sizeof(vis));    for(i=1;i<=n;i++)        dis[i]=ma[s][i];    vis[s]=1;    for(i=1;i
        
         ma[pos][j]+dis[pos])//算法关键                dis[j]=ma[pos][j]+dis[pos];        }    }    if(dis[e]!=inf)        printf("%d\n",dis[e]);    else        printf("-1\n");}int main(){    int i,j;    int x,y,z;    while(~scanf("%d %d",&n,&m))    {        for(i=1;i<=n;i++)        {            for(j=1;j<=n;j++)            {                ma[i][j]=inf;                if(i==j)                    ma[i][j]=0;            }        }        for(i=0;i
         
          z)                ma[x][y]=ma[y][x]=z;        }        dij();    }    return 0;}