如何找到从A点到B点的最长路径？

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

C+Time Limit: 7000ms Memory limit: 65536K 有疑问？点这里^_^+题目描述+给出一个带权无向图，包含n个点，m条边。求s到e的最短路径，保证最短路径存在。+输入+对于每组数据。+第一行输入n（1≤n≤1000）+第二行输入m（1≤m≤5000）+接下来m行，每行两个整数u和v，表示有一条边连接点u和点v。+输出+输出最短路径长度。

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; }