HDUOJ --2544最短路（基础）-白红宇

HDUOJ --2544最短路（基础）

阅读量：5161 次

发布时间：2019-06-13

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

输入包括多组数据。每组数据第一行是两个整数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条商店到赛场的路线。

Output

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

Sample Input

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

Sample Output

3 2

Source

代码：基于数组（时间复杂度为O（n^2））

1 #include
      
        2 #include
       
         3 const int inf=0x3f3f3f3f ; 4 int path[101]; 5 int sta[101][101],lowcost[101]; 6 void Dijkstra( int cost[][101], int n ) 7 { 8     int i,j,min; 9     int vis[101]={
    1};10     for(i=0; i

View Code

采用以为数组，时间复杂度将为O(n*long(n));

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int inf=0x3f3f3f3f;const int tol=101;const int edg=10001;int cost[edg],dist[tol];   /* 
           
             */int e,pnt[edg],nxt[edg],prev[tol],head[tol],vis[tol];struct qnode{ int v ,c; qnode(int vv=0 ,int cc=0):v(vv),c(cc){}; bool operator <(const qnode& r)const { return c>r.c; }};void Dijkstra(int n , const int src) /* 
            
              */{ qnode mv ; //充当一个临时变量 int i,j,k,pre; priority_queue
             
              que ; /*
              
               优先队列>*/ vis[src]=1; dist[src]=0; que.push( qnode(src,0) ); for( pre=src,i=1; i

View Code

转载于:https://www.cnblogs.com/gongxijun/p/3574556.html

你可能感兴趣的文章

SpringBoot 使用 MyBatis 分页插件 PageHelper 进行分页查询