图结构练习——最短路径

PRoblem Description

Input

Output

Example Input

3 21 2 11 3 11 0
Example Output
10
 
#include<stdio.h>#include<string.h>#include<stdlib.h>#define maxn 110#define max 0x3f3f3f3fint df[maxn][maxn];int book[maxn];int dist[maxn];int n;void dijkstra(int vo){    int i,j,k,min,u;    for(i=1;i<=n;i++)    {        dist[i]=df[vo][i];    }    book[vo]=1;    dist[vo]=0;    for(i=2;i<=n;i++)    {        min=max; u=vo;        for(j=1;j<=n;j++)        {            if(dist[j]<min&&book[j]==0)            {                u=j;                min=dist[j];            }        }        book[u]=1;        for(k=1;k<=n;k++)        {            if((dist[k]>dist[u]+df[u][k])&&book[k]==0&&df[u][k]<max)            {                dist[k]=dist[u]+df[u][k];            }        }    }}int main(){    int m;    int i,j,u,v,w;    while(scanf("%d%d",&n,&m)!=EOF)    {        memset(df,max,sizeof(df));        memset(book,0,sizeof(book));        for(i=1;i<=n;i++)        {            df[i][i]=0;        }        while(m--)        {            scanf("%d%d%d",&u,&v,&w);            if(df[u][v]>w)                df[u][v]=df[v][u]=w;        }        dijkstra(1);        printf("%d/n",dist[n]);    }    return 0;}