Alice拜年模板题 /// 最短路Dijk oj1344

题目大意：

大年初一，Alice带上拜年礼物去给N-1位亲朋好友长辈拜年，亲友真多啊，是个大家族。由于Alice才2岁，力气不大，每次只能拿一份礼物，拜完年之后，要回家取第二份礼物，然后去下一家拜年（无语了）。为了表示对亲朋长辈的尊敬，Alice每次都从家步行去到对方家里，拜完年由爸爸骑自行车带回家（彻底无语）。可怜天下父母心啊，爸爸全程陪着Alice折腾。

假设Alice的住址编号为1，各亲朋好友的家分别编号为 2 ~ N 。这个城市的道路都是单向的（别惊奇，这个世界无奇不有），共有M条道路，每条道路长短不一。求Alice给这 N-1 个家庭拜完年，最少步行了多少路程？

Input

输入的第一行是两个整数 N 和 M，1 ≤ N ≤ 1000， 1 ≤ M ≤ 100000

接下来M行，每行3个正整数 U ，V ，W ，表示该条道路是从节点U到节点V的，这条道路共有W米。满足 1 ≤ U, V ≤ N ， 1 ≤ W ≤ 10000 ，保证任意两点都能互相到达。

注意本题有重边。

Output

输出一行，包含一个整数，为Alice最少步行的路程。

Sample Input

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

Sample Output

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

int n,m,a[][];

int dis[],flag[];

void dijk()

{

    for(int i=;i<n;i++)

    {

        int mini=INF,u;

        for(int j=;j<=n;j++)

            if(!flag[j]&&dis[j]<mini)

            {

                mini=dis[j];

                u=j;

            }

        if(mini==INF) break;

        flag[u]=;

        for(int j=;j<=n;j++)

            if(dis[j]>dis[u]+a[u][j]&&!flag[j]&&a[u][j]<INF)

                dis[j]=dis[u]+a[u][j];

    }

}

int main()

{

        scanf("%d%d",&n,&m);

        int u,v,w,sum=;

        memset(a,INF,sizeof(a));

        memset(flag,,sizeof(flag));

        memset(dis,INF,sizeof(dis));

        for(int i=;i<=m;i++)

        {

            scanf("%d%d%d",&u,&v,&w);

            a[u][v]=min(w,a[u][v]);  /// 有重边 取小

        }

        for(int i=;i<=n;i++)

            dis[i]=a[][i];    /// dis[i]=a[起点][i]

        dis[]=;

        flag[]=;

        dijk();

        for(int i=;i<=n;i++)

            sum+=dis[i];

        printf("%d",sum);

    return ;

}

Dijkstra求最短路+输出路径模板 http://www.cnblogs.com/Rubbishes/p/7687600.html

Alice

Alice拜年 模板题 /// 最短路Dijk oj1344

Alice拜年模板题 /// 最短路Dijk oj1344