首页 > 试题广场 >

HDU 2544 最短路

[编程题]HDU 2544 最短路
  • 热度指数：1565 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？


输入描述:
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
       
输入保证至少存在1条商店到赛场的路线。


输出描述:
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
示例1

输入

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

输出

3
2
算法知识视频讲解
添加回答
推荐
雨樱花28头像 雨樱花28 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 1000000
using namespace std;
int city,road;
int mapp[205][205];
int spand[205];
int select[205];
void dij(int city)
{
    int minn,k,i,j;
    memset(select,0,sizeof(select));
    for(i=1;i<=city;i++)
    spand[i]=mapp[1][i];
    spand[1]=0;select[1]=1;
    for(i=2;i<=city;i++)
    {
        minn=INF;k=-1;
        for(j=1;j<=city;j++)
        {
            if(!select[j]&&spand[j]<minn)
            {
                k=j;minn=spand[j];
            }
        }
        if(k==-1)break;
        select[k]=1;
        for(j=1;j<=city;j++)
        {
            if(spand[j]>spand[k]+mapp[k][j]&&!select[j])
            spand[j]=spand[k]+mapp[k][j];
        }
    }
    printf("%d\n",spand[city]);
}
int main()
{
    int i;int x,y,z;
    while(scanf("%d%d",&city,&road)!=EOF)
    {
        if(city==0||road==0)
        break;
        memset(mapp,INF,sizeof(mapp));
        memset(spand,INF,sizeof(spand));
        for(i=1;i<=road;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(mapp[x][y]>z||mapp[y][x]>z)
            {
                mapp[x][y]=z;mapp[y][x]=z;
            }
        }
        dij(city);
    }
    return 0;
}
发表于 2015-10-28 15:17:39 回复(0)
C/C++
hooli头像 hooli 
/******************************* Floyd ******************************/
#include <stdio.h>
#define INF 0x7FFFFFFF
int dist[100][100];
int main() {
	int N, M;
	while (~scanf("%d%d", &N, &M)) {
		if (!N && !M)break;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(i!=j)dist[i][j] = INF;
				else dist[i][j] = 0;
			}
		}
		int a, b, cost;
		while (M--) {
			scanf("%d%d%d", &a, &b, &cost);
			dist[a-1][b-1] = dist[b-1][a-1] = cost;
		}
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if ((dist[i][k] == INF || dist[k][j] == INF)||(i==j))continue;
					dist[i][j] = dist[i][j] < dist[i][k] + dist[k][j] ? dist[i][j] : dist[i][k] + dist[k][j];
				}
			}
		}
		printf("%d\n", dist[0][N - 1]);
	}
	return 0;
}


/*******************************  Dijkstra ******************************/
#include <stdio.h>
#include <memory.h>
#define INF 0x7FFFFFFF
int dist[100][100];
bool flag[100];
int main() {
	int N, M;
	while (~scanf("%d%d", &N, &M)) {
		if (!N && !M)break;
		memset(flag, false, N);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(i!=j)dist[i][j] = INF;
				else dist[i][j] = 0;
			}
		}
		int a, b, cost;
		while (M--) {
			scanf("%d%d%d", &a, &b, &cost);
			dist[a-1][b-1] = dist[b-1][a-1] = cost;
		}
		flag[0] = true;
		int min, tmp = 1;
		for (int i = 1; i < N; i++) {
			min = INF;
			for (int j = 1; j < N; j++) {
				if (flag[j])continue;
				if (dist[0][j] < min) {
					min = dist[0][j];
					tmp = j;
				}
			}
			flag[tmp] = true;
			if (tmp == N - 1)break;
			for (int j = 1; j < N; j++) {
				if (flag[j]||dist[tmp][j]==INF)continue;
				if (dist[0][tmp] + dist[tmp][j] < dist[0][j])dist[0][j] = dist[0][tmp] + dist[tmp][j];
			}
		}
		printf("%d\n", dist[0][N - 1]);
	}
	return 0;
}

编辑于 2017-02-28 00:05:02 回复(0)
时光是影子的眼头像 时光是影子的眼 
#include<stdio.h>
int ans[101][101];
int main() {
    int n,m;
    while (scanf("%d%d", &n,&m) != EOF){
        if (n == 0 || m == 0)break;
        for(int i=1;i<=n;i++){
            for (int j = 1; j <= n; j++)
                ans[i][j] = -1;
            ans[i][i] = 0;
        }//初始化；
        
        int a, b, c;
        while(m--) {
            scanf("%d%d%d", &a, &b, &c);
            ans[a][b] = ans[b][a] = c;
        }//赋值
        for(int k=1;k<=n;k++){
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (ans[i][k] == -1 || ans[k][j] == -1) continue;
                    if (ans[i][j] == -1 || ans[i][j] > ans[i][k] + ans[k][j])
                        ans[i][j] = ans[i][k] + ans[k][j];
                }
            }
        }
        printf("%d\n", ans[1][n]);
    }
    return 0;
}

发表于 2018-03-09 13:08:14 回复(0)
C/C++
鱼香-肉丝头像 鱼香-肉丝 
//Floyd算法
#include<bits/stdc++.h>
using namespace std;
int ans[102][102];
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(m==0&&n==0) break;
        for(int i=1;i<=n;i++)//初始化图的邻接矩阵
        {
            for(int j=1;j<=n;j++)
                ans[i][j]=-1;
            ans[i][i]=0;
        }
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            ans[a][b]=c;
            ans[b][a]=c;
        }
        //floyd算法
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(ans[i][k]==-1||ans[k][j]==-1) continue;
                    else if(ans[i][j]==-1 || ans[i][j]>ans[i][k]+ans[k][j])
                        ans[i][j]=ans[i][k]+ans[k][j];
                }
            }
        }
        cout<<ans[1][n]<<endl;
    }
    return 0;
}
发表于 2020-02-17 11:22:46 回复(0)
C/C++
猪二娃乔治头像 猪二娃乔治

邻接矩阵实现的 Dijkstra, Floyd, Bellman-Ford 大礼包

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int dijkstra(vector<vector<int>> &adjMatrix, int n, int m, int s, int t) {
    // n 个点，m 条边
    vector<bool> isFixed(n + 1, false);
    vector<int> dist(n + 1, INT_MAX);

    // 初始化 dist 数组，表示各点到原点的最短距离
    for (int i = 1; i <= n; ++i)
        dist[i] = adjMatrix[1][i];

    // 初始化点集合信息，将 1 号点标记为 true
    isFixed[s] = true;

    // dijkstra
    for (int i = 1; i < n; ++i) { // 总共会处理 n-1 个点
        // 1. 找到当前 dist 数组中未加入解集点中到起点距离最小的点
        //    这里可以使用堆结构进行优化
        int minDist = INT_MAX;
        int minVertex = 1;
        for (int i = 0; i <= n; ++i) {
            if (dist[i] < minDist && isFixed[i] == false) {
                minDist = dist[i];
                minVertex = i;
            }
        }

        // 2. 将该点加入解集
        isFixed[minVertex] = true;

        // 3. 松弛该点的邻接边
        //    这里可以使用邻接表优化
        for (int j = 1; j <= n; ++j) {
            if (adjMatrix[minVertex][j] < INT_MAX) {
                dist[j] = min(dist[j], dist[minVertex] + adjMatrix[minVertex][j]);
            }
        }
    }

    return dist[t];
}

int floyd(vector<vector<int>> &adjMatrix, int n, int m, int s, int t) {
    // 通过前 k 个点进行中转
    for (int k = 1; k <= n; ++k) {
        // i->j 的最短路
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                // 若中途有路径不可达则跳过
                if (i == j || adjMatrix[i][k] == INT_MAX || adjMatrix[k][j] == INT_MAX)
                    continue;
                // 否则选择更短的路径
                adjMatrix[i][j] = min(adjMatrix[i][j], adjMatrix[i][k] + adjMatrix[k][j]);
            }
        }
    }

    return adjMatrix[s][t];
}

int bellmanFord(vector<vector<int>> &adjMatrix, int n, int m, int from, int to) {
    // n 个点，m 条边（这里使用邻接矩阵，m 没用上）
    // 初始化 dist 数组，表示各点到原点的最短距离
    vector<int> dist(n + 1, INT_MAX);
    dist[from] = 0;

    // 对所有的 m 条边都进行 n-1 轮松弛 O(V)
    for (int i = 1; i < n; ++i) {
        bool relaxed = false;
        // 每轮松弛所有的边，由于采用了邻接矩阵表示，因此只能遍历二维矩阵 O(E)
        // 因此这里采用邻接表表示会更方便
        for (int s = 1; s <= n; ++s) {
            for (int t = 1; t <= n; ++t) {
                // 跳过不存在的边
                if (s == t || adjMatrix[s][t] == INT_MAX) continue;

                // 松弛边，也就是松弛边的 to 节点
                if (dist[s] != INT_MAX && dist[t] > dist[s] + adjMatrix[s][t]) {
                    dist[t] = dist[s] + adjMatrix[s][t];
                    relaxed = true;
                }
            }
        }
        // 如果这一轮没有发生松弛，则找到所有最短路，提前终止
        if (relaxed == false) break;
    }

    return dist[to];
}

int main() {

    // 输入图的点数和边数
    // 点表示为 1,2,3,...,N
    int v, e;
    while (cin >> v >> e && (v != 0 && e != 0)) {
        int n = v, m = e;
        // 图的邻接矩阵
        vector<vector<int>> adjMatrix(v + 1, vector<int>(v + 1, INT_MAX));
        // 初始化邻接矩阵
        for (int i = 1; i <= v; ++i)
            adjMatrix[i][i] = 0;

        // 每条边的起点，终点和花费
        int s, t, c;
        while (e--) {
            cin >> s >> t >> c;
            // 这里是无向图，需要更新两个方向
            // 如果是有向图就只需要更新输入的方向就行了
            adjMatrix[s][t] = c;
            adjMatrix[t][s] = c;
        }
        // 将图和求解目标输入算法求解
        int opt = dijkstra(adjMatrix, n, m, 1, n);
//        int opt = floyd(adjMatrix, n, m, 1, n);
//        int opt = bellmanFord(adjMatrix, n, m, 1, n);
        cout << opt << endl;
    }

    return 0;
}
发表于 2019-08-06 20:24:15 回复(0)
看不见的风景20180328190441头像 看不见的风景20180328190441
#include <iostream>
#include<string.h>
#define inf 99999999
using namespace std;
int n,m;//点，边
int main()
{
    while(cin>>n&&cin>>m)
    {
        if(n+m==0)return 0;
        int dist[110][110],i,j,k,a,b,c;
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        dist[i][j]=inf;
        for(i=1;i<=m;i++)
        {
            cin>>a>>b>>c;
            dist[a][b]=c;
            dist[b][a]=c;
        }
        for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        cout<<dist[1][n]<<endl;
    }
 } 
发表于 2019-01-24 21:24:15 回复(0)
天才小芒果头像 天才小芒果 
#include<iostream>
#include<vector>
#include<limits.h>
#define N 101
using namespace std;
struct edge{ //邻接表边节点 
    int next;
    int time;
};
vector<edge> Edges[N];
bool mark[N];//标记已经是最短路径的点 
int dis[N]; //保存1号点到其他各个点的最短距离 
void init(int n){
    for(int i=1;i<=n;i++){
        dis[i]=-1;        //-1表示无穷
        mark[i]=false;    //未扩展 
    }
}
int main(){
    int n,m;
    int a,b,t;
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        for(int i=1;i<N;i++){
            Edges[i].clear();//初始化，清空容器中的内容 
        }
        for(int i=1;i<=m;i++){ //创建无向图邻接表 
            cin>>a>>b>>t;
            edge temp;
            temp.time=t;
            temp.next=b;
            Edges[a].push_back(temp);
            temp.next=a;
            Edges[b].push_back(temp);
        } 
        
        init(n);//初始化距离数组以及标记数组 
        int p=1;  //p保存当前选择节点,从1号点开始 
        int x=n-1;
        dis[p]=0;
        mark[p]=true; 
        
        while(x--){    //加入n-1次节点 
            int min=INT_MAX;
            for(int j=0;j<Edges[p].size();j++){//对所有与当前节点相接的节点k尝试进行松弛操作
                 int k=Edges[p][j].next;
                 if(mark[k]==true) continue;//已经是最短路径集合中的点，跳过 
                 if(dis[k]==-1||dis[p]+Edges[p][j].time<dis[k]){ //比较大小，更新最短距离 
                     dis[k]=dis[p]+Edges[p][j].time;
                }    
            }
            for(int i=1;i<=n;i++){    
                if(mark[i]==false&&dis[i]!=-1&&dis[i]<min){ //选择待扩展点中距离最短的点加入集合中 
                    min=dis[i];
                    p=i;
                }
            }
            mark[p]=true;
        }
        cout<<dis[n]<<endl;
        
    }
    return 0;
}
Dijstra算法，时间复杂度为o(n*n)
发表于 2019-01-09 11:17:40 回复(0)
victorytein头像 victorytein
dalao们帮忙看下这个为啥死活不能通过所有的测试用例啊？检查了N遍了，感觉没有问题啊。。。 
#include <iostream>
using namespace std;
const int maxn = 100+5;
int arr[maxn][maxn];

int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;

        //初始化，所有节点之间不可达
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] == -1;
            }
            arr[i][i] = 0;
        }

        while (m--) {
            int a, b, c;
            cin >> a >> b >> c;
            arr[a][b] = c;
             arr[b][a] = c;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (arr[i][k] == -1 || arr[k][j] == -1) continue;
                    if (arr[i][j] == -1 || (arr[i][k]+arr[k][j]) < arr[i][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

        cout << arr[1][n] << endl;
    }



    return 0;
}

发表于 2018-06-24 17:16:49 回复(1)
C/C++
牛客7464386号头像 牛客7464386号
#include<stdio.h>
int e[101][101];
#define INF 123123123
int main(){
int i,j,n,m;
while(scanf("%d%d",&n,&m),n!=0&&m!=0){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
e[i][j]=INF;
}
e[i][i]=0;
}
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[a][b]=e[b][a]=c;
}
for(int k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
if(e[i][k]+e[k][j]<e[i][j])
e[i][j]=e[i][k]+e[k][j];
}
printf("%d\n",e[1][n]);
}
}
=================================dijkstra===========================
#include<stdio.h>
#include<vector>
#define INF 123123123
using namespace std;
struct Edge{
    int next,cost;
};
vector<Edge> edge[101];
bool set[101];
int dis[101];

int main(){
    int n,m,i,j;
    while(scanf("%d%d",&n,&m),n+m){
        for(i=1;i<=n;i++){
            edge[i].clear();
        }
        while(m--){
            int a,b,cost;
            scanf("%d%d%d",&a,&b,&cost);
            Edge tmp;
                tmp.next=b;
                tmp.cost=cost;
            edge[a].push_back(tmp);
                tmp.next=a;
            edge[b].push_back(tmp);
        }
        for(i=1;i<=n;i++){
            set[i]=false;
            dis[i]=INF;
        }        
        set[1]=true;
        dis[1]=0;
        int newp=1;                        
        for(i=1;i<n;i++){//循环n-1次， 每一轮循环，找到距离1号结点最近的一个节点，将之并入定点集set 
            for(j=0;j<edge[newp].size();j++){        //遍历与newp结点相连的边，更新边上另一点到i的距离dis[i] 
                int node=edge[newp][j].next;        //该边的另一个结点node
                int cost=edge[newp][j].cost;        //该边的权值 
                    if(set[node]==false&&dis[newp]+cost<dis[node]){    //dis[node]为点1到点node的距离 
                        dis[node]=dis[newp]+cost;
                    }
            }
            int min=INF;
            for(int i=1;i<=n;i++){//在以newp为中间点的路径上，找到距离i最小的结点 
                if(set[i]==false&&dis[i]<min){
                    min=dis[i];
                    newp=i;    
                }
            } 
            set[newp]=true;
        }
        printf("%d\n",dis[n]);
    }
}

编辑于 2018-02-19 18:10:15 回复(0)
C/C++
塞拉门尼斯头像 塞拉门尼斯 
#include<stdio.h>
#include<vector>
#define INF 0x7FFFFFFF  //设置一个int的最大值，之后用于赋值给min来进行比较

using namespace std;

struct Edge
{
    int next;
    int cost;
};
vector<Edge> edge[101];  /*这里用了vector，也就是说用邻接表法来构造图，
               vector用法可以访问Cplusplus.com，为统一起见
             定义101个表头。*/

int main()
{
    int dis[101];       /*定义起始点到终点的距离，mark表示集合，每得到
                  一个点的最短路径，就加入mark[]中*/
    bool mark[101];      //因为一会儿以i=1开始访问节点，所以定义101个
    
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF)      //输入路口数，和路径数
    {
      if(n == 0 && m == 0)          //为0结束程序
            break;
      for(int i = 0; i<n; i++)        //对vector初始化
            edge[i].clear();
        for(int i = 0; i<m; i++)        //输入边的信息
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            Edge temp;
            temp.cost = c;
            temp.next = a;
            edge[b].push_back(temp);
            temp.next = b;
            edge[a].push_back(temp);
        }
        
        for(int i = 1; i<=n ;i++)
        {
            mark[i] = false;
            dis[i] = -1;
        }
        
        int newPoint = 1;        //newPoint用于存放每次新加入的点
        mark[newPoint] = true;      //把第一个点设为起始点，先加入集合中
        dis[newPoint] = 0;
        
        for(int i = 1; i<n; i++)    //对剩余点进行遍历    
        {    for(int j = 0; j<edge[newPoint].size(); j++)    //遍历当前点所连接的所有边
            {                          
                int next = edge[newPoint][j].next;
                int cost = edge[newPoint][j].cost;
                if(mark[next] == true)         //如果该边所连接的点已在集合中，不做处理
                    continue;
                if(dis[next] == -1 || cost + dis[newPoint]<dis[next])//前一句dis[next]==-1说明当前遍历到的边，其next所指示的点
                {                              //是之前无法到达的，或者有更短的路
                    dis[next] = cost + dis[newPoint];
                }
            }
            int min = INF;
            for(int j = 1; j<=n; j++)
            {
                if(mark[j])
                    continue;
                if(dis[j] == -1)
                    continue;
                if(min>dis[j])     //找到本次遍历中找到的最短路
                {    
                    min = dis[j];
                    newPoint = j; //暂定最小值点，如有更小的会更新
                }
            }
            mark[newPoint] = true;    //上一个for结束后，newPoint即为新加的点
        }//主要循环
        printf("%d\n",dis[n]);
    }//while
    return 0;
}
用的是Dijstra，存储方式是邻接表。用不来这个编辑器啊！(╯°Д°)╯︵┻━┻
编辑的时候可能有点小问题，大家见谅(｀・ω・´)
发表于 2018-01-23 21:17:53 回复(0)
C/C++
|讨厌鬼|头像 |讨厌鬼|
还是Floyd写起来快 
#include<stdio.h>
#define N 101
int ans[N][N];
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0) break;
        int i,j;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                ans[i][j]=-1;
        while(m--){
            int a,b,tmp;
            scanf("%d%d%d",&a,&b,&tmp);
            ans[a][b]=tmp;
            ans[b][a]=tmp;
        }
        int k;
        for(k=1;k<=n;k++)
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++){
                    if(ans[i][k]==-1||ans[k][j]==-1) continue;
                    if(ans[i][j]==-1||ans[i][k]+ans[k][j]<ans[i][j])
                        ans[i][j]=ans[i][k]+ans[k][j];
                }
        printf("%d\n",ans[1][n]);
    }
    return 0;
} 

发表于 2018-01-22 22:22:45 回复(0)
Java
ʚ😠ɞ3头像 ʚ😠ɞ3 
import java.util.*; public class Dijkstra{ static class Node{ int value;
        ArrayList<Node> nodes;
        ArrayList<Edge> edges;
        Node(int value){ this.value = value; nodes = new ArrayList<>(); edges = new ArrayList<>();
        } @Override  public String toString() {
            String res=value+":"; for(Node node:nodes){
               res += node.value+" ";
            }
            res+="\n"; return res;
        }
    } static class Edge{
        Node from;
        Node to; int cost;
        Edge(Node from,Node to,int cost){ this.from = from; this.to = to; this.cost = cost;
        }
    } public static void main(String[] args) {
        Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int m = in.nextInt(); if(n==0&&m==0){ break;
            }
            HashMap<Integer,Node> nodes = new HashMap<>();
            HashSet<Edge> edges = new HashSet<>(); for(int i=1;i<=m;i++){ int from = in.nextInt(); int to = in.nextInt(); int cost = in.nextInt(); if(!nodes.containsKey(from)){
                    nodes.put(from,new Node(from));
                } if(!nodes.containsKey(to)){
                    nodes.put(to,new Node(to));
                }
                Node fromNode = nodes.get(from);
                Node toNode = nodes.get(to);
                Edge edge = new Edge(fromNode,toNode,cost);
                Edge edge2 = new Edge(toNode,fromNode,cost);
                fromNode.nodes.add(toNode);
                fromNode.edges.add(edge);
                fromNode.edges.add(edge2);
                toNode.nodes.add(fromNode);
                toNode.edges.add(edge);
                toNode.edges.add(edge2);
            }
            HashMap<Node,Integer> distanceMap = new HashMap<>();
            HashSet<Node> selectedNodes = new HashSet<>();
            Node head = nodes.get(1);
            distanceMap.put(head,0);
            Node minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes); while (minNode!=null){ int distance = distanceMap.get(minNode); for(Edge edge:minNode.edges){
                    Node toNode = edge.to; if(!distanceMap.containsKey(toNode)){
                        distanceMap.put(toNode,distance+edge.cost);
                    }
                    distanceMap.put(toNode,Math.min(distanceMap.get(toNode),distance+edge.cost));
                }
                selectedNodes.add(minNode);
                minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
            }
            System.out.println(distanceMap.get(nodes.get(n)));
        }
    } private static Node getMinDistanceAndUnselectedNode(
            HashMap<Node, Integer> distanceMap,
            HashSet<Node> selectedNodes) {
        Node minNode = null; int minDistance = Integer.MAX_VALUE; for(Map.Entry<Node,Integer> entry:distanceMap.entrySet()){
            Node node = entry.getKey(); int distance = entry.getValue(); if(!selectedNodes.contains(node)&&distance<minDistance){
                minNode = node;
                minDistance = distance;
            }
        } return minNode;
    }
}
编辑于 2017-12-18 02:54:38 回复(0)
新世纪的神头像 新世纪的神 
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10005;
const int INF=1e7;
struct edge{
    int from,to,cost;
};
edge es[2*maxn];
int N,M,d[maxn];
void shortest_path(int s){
    fill(d,d+N+1,INF);
    d[1]=0;
    while(true){
        bool ok=false;
        for(int i=1;i<=2*M;i++){
            edge e1=es[i];
            if(d[e1.from]!=INF&&d[e1.to]>d[e1.from]+e1.cost){
                d[e1.to]=d[e1.from]+e1.cost;
                ok=true;
            }
        }
        if(!ok) break;
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2&&N){
        for(int i=1;i<=M;i++){
            scanf("%d%d%d",&es[2*i-1].from,&es[2*i-1].to,&es[2*i-1].cost);
            es[2*i].from=es[2*i-1].to;
            es[2*i].to=es[2*i-1].from;
            es[2*i].cost=es[2*i-1].cost;
        }
        shortest_path(1);
        printf("%d\n",d[N]);
    }
    return 0;
}
用的Bellman-Ford算法，复杂度O(N*M)。 
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=105;
const int INF=1e6;
bool vis[maxn];
int d[maxn];
int cost[maxn][maxn];
int n,m;
void shortest_path(){
    while(true){
        int v=-1;
        for(int u=1;u<=n;u++){
            if(!vis[u]&&(v==-1||d[u]<d[v]))
                v=u;
        }
        if(v==-1) break;
        vis[v]=true;
        for(int u=1;u<=n;u++){
            d[u]=min(d[u],d[v]+cost[v][u]);
        }
    }
}
void init(){
    fill(vis,vis+n+1,false);
    fill(d,d+n+1,INF);
    d[1]=0;
    for(int i=1;i<=n;i++){
        fill(cost[i],cost[i]+n+1,INF);
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)==2&&n){
        int from,to,c;
        init();
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&from,&to,&c);
            cost[from][to]=cost[to][from]=c;
        }
        shortest_path();
        printf("%d\n",d[n]);
    }
    return 0;
}
Dijkstra算法算法  复杂度O(N^2)
编辑于 2016-08-04 16:47:40 回复(0)
提交观点

问题信息

难度：
13条回答 3730浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号