学步园

第一次接触最短路问题，折腾了一下午，基本框架出来了，可总是卡在一些细节。。。

关键最后还有一个可能有重复路段，需要取其中最小值。。。伤不起

#include<stdio.h>
#include<string.h>
#define mi 9999999
#define min(a,b) (a>b? b:a)
int map[202][202];
int vis[202];
int divs[202];
int ans;
int n,m;

void prim(int b)
{
    int k;
    for(int j=1; j<n; j++)
    {
        int min=mi;
        for(int i=0; i<n; i++)
            if(!vis[i]&&min>divs[i])
            {
                min=divs[i];
                k=i;
            }
        vis[k]=1;
        for(int i=0; i<n; i++)
            if(!vis[i]&&divs[k]+map[k][i]<divs[i])
                divs[i]=divs[k]+map[k][i];
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(vis,0,sizeof(vis));
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
                map[i][j]=mi;
            map[i][i]=0;
        }
        int a,b,c;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=min(map[a][b],c);
            map[b][a]=min(map[b][a],c);
        }
        scanf("%d%d",&a,&b);
        for(int i=0; i<n; i++)
            divs[i]=map[a][i];
        divs[a]=0;
        prim(b);
        printf("%d\n",divs[b]==mi?-1:divs[b]);
    }
    return 0;
}

后来，在学习spfa算法的时候，又回头做了这道题。

附上代码：

#include<stdio.h>
#include<string.h>
#include<queue>

using namespace std;

int map[202][202];
int vis[202];
int d[202];

int n,m;
int s,e;

void spfa()
{
    queue <int>  q;
    int a;
    q.push(s);
    for(int i=0; i<n; i++)
        d[i]=0x7ffffff;
    d[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        a=q.front();
        q.pop();
        vis[a]=0;
        for(int i=0; i<n; i++)
        {
            if(d[i]>map[a][i]+d[a])
            {
                d[i]=map[a][i]+d[a];
                //printf("**%d  %d   %d  %d\n",i,d[i],map[a][i],d[a]);
                if(!vis[i])
                {
                    q.push(i);
                    vis[i]=1;
                }
            }
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int a,b,c;
        memset(vis,0,sizeof(vis));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                map[i][j]=0x7ffffff;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=map[a][b]>c?c:map[a][b];
        }
        scanf("%d%d",&s,&e);
        spfa();
        if(d[e]==0x7ffffff)
            printf("-1\n");
        else
            printf("%d\n",d[e]);
    }
    return 0;
}