本文共 1399 字，大约阅读时间需要 4 分钟。

原题链接：

一：原题内容

2 11 2 33 31 2 52 3 53 1 20 0

32

二：分析理解

一个简单的单源最短路径问题。

三：AC代码

#include
   
      #include
    
     #include
     
        using namespace std;int N;int M;int A, B, C;int a[105][105];int visited[105];int ans[105];int main(){	while (scanf("%d%d", &N, &M) && (N || M))	{		memset(visited, 0, sizeof(visited));		memset(a, 0, sizeof(a));		memset(ans, 0, sizeof(ans));		for (int i = 0; i < M; i++)		{			scanf("%d%d%d", &A, &B, &C);			a[A][B] = a[B][A] = C;		}		//Dijkstra		for (int i = 2; i <= N; i++)		{			if (a[1][i]>0)				ans[i] = a[1][i];			else				ans[i] = INT_MAX;		}		visited[1] = 1;		for (int i = 1; i <= N - 1; i++)		{			int min = INT_MAX;			int minPos;			for (int j = 1; j <= N; j++)			{				if (!visited[j] && ans[j] < min)				{					min = ans[j];					minPos = j;				}			}			visited[minPos] = 1;			for (int k = 1; k <= N; k++)			{				if (!visited[k] && a[minPos][k]>0 && a[minPos][k] + min < ans[k])					ans[k] = a[minPos][k] + min;			}		}		printf("%d\n", ans[N]);	}	return 0;}
     
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51014013 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！