请问如何找到两点之间的最短路径？

本文共计685个文字，预计阅读时间需要3分钟。

pythonC++ Time Limit: 7000ms Memory limit: 65536K 有疑问？点这里^_^题目描述给出一个带权无向图，包含n个点和m条边。求出点s到点e的最短路径，并保证最短路径存在。输入对于每组数据。第一行输入n（1≤n≤10000），m（1≤m≤200000），s（1≤s≤n），e（1≤e≤n）。接下来m行，每行三个整数a，b，c（1≤a，b≤n，c≥0），表示图中存在一条从a到b的边，边权为c。输出对于每组数据，输出s到e的最短路径的长度，即所求的s到e的最短路径上的边的权重之和。

输入示例

67 1 5

12 3

23 3

24 1

34 2

35 3

45 3

46 3

输出示例

6

C

Time Limit: 7000ms Memory limit: 65536K有疑问？点这里^_^

题目描述

给出一个带权无向图，包含n个点，m条边。求出s，e的最短路。保证最短路存在。

输入

对于每组数据。

第一行输入n，m(1<= n && n<=5*10^5,1 <= m && m <= 2*10^6)。
接下来m行，每行三个整数，u,v,w,表示u，v之间有一条权值为w(w >= 0)的边。
最后输入s，e。

输出

对于每组数据输出一个整数代表答案。

示例输入

3 1 1 2 3 1 2

示例输出

3

提示

来源

zmx

示例程序

#include<stdio.h> #include <iostream> #include<string.h> #include<stdlib.h> #define INF 100001 using namespace std; int n,m; int t; int num[500002]; struct node { int x,y,z; } q[4000002]; void add(int xx,int yy,int zz) { q[t].x = xx; q[t].y = yy; q[t].z = zz; t++; q[t].x = yy; q[t].y = xx; q[t].z = zz; t++; } void BF(int s,int e) { int i,j; for(i=0; i<=n; i++) { num[i] = INF; } num[s] = 0; int flag; for(i=1; i<n; i++) { flag = 0; for(j=0; j<t; j++) { if(num[q[j].y]>num[q[j].x] + q[j].z) { num[q[j].y] = num[q[j].x] + q[j].z; flag = 1; } } if(flag == 0) break; } printf("%d\n",num[e]); return ; } int main() { int i,x,y,z; while(scanf("%d%d",&n,&m)!=EOF) { t = 0; while(m--) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); } scanf("%d%d",&x,&y); BF(x,y); } return 0; }