最短路

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

【文章原创作者：香港云服务器 http://www.558idc.com/ne.html 复制请保留原URL】