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[1005][1005];
int dis[1005],flag[1005];
void dijk()
{
    for(int i=1;i<n;i++)
    {
        int mini=INF,u;
        for(int j=1;j<=n;j++)
            if(!flag[j]&&dis[j]<mini)
            {
                mini=dis[j];
                u=j;
            }
        if(mini==INF) break;
        flag[u]=1;
        for(int j=1;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=0;
        memset(a,INF,sizeof(a));
        memset(flag,0,sizeof(flag));
        memset(dis,INF,sizeof(dis));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            a[u][v]=min(w,a[u][v]);  /// 有重边 取小
        }
        for(int i=1;i<=n;i++)
            dis[i]=a[1][i];    /// dis[i]=a[起点][i]
        dis[1]=0;
        flag[1]=1;
        dijk();
        for(int i=1;i<=n;i++)
            sum+=dis[i];
        printf("%d",sum);

    return 0;
}

View Code

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

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

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