题目意思大概是给出T条边,N个点。求第一个点到第N个点的最短距离。开始是n*n次直接循环,然后挂了,总是出现莫名其妙的数字(memset造成,memset使用要谨慎啊!!!)。后来看博客发现用Dijkstra算法求。从1开始,找出距离当前位置距离最小而且最远的点,然后通过这个点找他能到达的边的距离和当前距离相加,若有更短的距离则更新这个距离,以此类推。求解的时候要注意去重复。

题目:飞机票直达(C - Til the Cows Come Home


下面是代码:

Memory: 4064 KB
Time: 94 MS
Language: C++
Result: Accepted
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=1000+1;

int dist[maxn][maxn], dis[maxn], flag[maxn];
int t, n, i, j;     //t:边,n:点
int x, y, len;

void Init()
{
    memset(dist, INF, sizeof(dist));
    memset(dis, INF, sizeof(dis));
    memset(flag, 0, sizeof(flag));
    for(i=1;i<=t;i++)
    {
        scanf("%d%d%d", &x, &y, &len);
        if(len<dist[x][y])              //如果小于才加进去
            dist[x][y]=dist[y][x]=len;
    }
}

void Dijkstra()
{
    dis[1]=0;
    for(i=1;i<=n;i++)
    {
        int cur=-1;
        for(j=1;j<=n;j++)
        {
            if(!flag[j]&&(cur==-1||dis[j]<dis[cur]))     //找到当前距离最小的那个位置
                cur=j;
        }
        flag[cur]=1;        //标记访问
        for(j=1;j<=n;j++)
        {
            if(!flag[j]&&dis[j]>dis[cur]+dist[cur][j])    //更新当前所有的位置
                dis[j]=dis[cur]+dist[cur][j];
        }
    }
}

int main()
{
    while(scanf("%d %d", &t, &n)!=EOF)
    {
        Init();
        Dijkstra();
        printf("%d\n", dis[n]);
    }
    return 0;
}