学步园

写一些要点供以后翻阅……转载请注明该文链接

题意：n个结点，m条无向边，给起点a终点b，求从a到b最短距离。

思路：直接邻接矩阵建图，跑一遍dijkstra或者spfa

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

using namespace std;

const int maxn=210;
const int inf=0x3f3f3f3f;

int E[maxn][maxn],n;
int d[maxn],p[maxn];

void Dijkstra(int s)
{
    bool vis[maxn];
    memset(vis,false,sizeof(vis));
    memset(d,inf,sizeof(d));
    memset(p,0,sizeof(p));
    d[s]=0;
    while(1)
    {
        int u=-1;
        for(int i=0;i<n;i++)
        {
            if(!vis[i] && (u==-1 || d[i]<d[u])) u=i;
        }
        if(u==-1 || d[u]==inf) break;
        vis[u]=true;
        for(int v=0;v<n;v++)
        {
            if(d[u]+E[u][v]<d[v])
            {
                d[v]=d[u]+E[u][v];
                p[v]=u;
            }
        }
    }
}

int main()
{
    int m,a,b,c;
    while(scanf("%d%d",&n,&m),n||m)
    {
        memset(E,inf,sizeof(E));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            a--,b--;
            E[a][b]=E[b][a]=c;
        }
        Dijkstra(0);
        printf("%d\n",d[n-1]);
    }
    return 0;
}