最短路

Problem Description

在每年的校赛里，全部进入决赛的同学都会获得一件非常美丽的t-shirt。

可是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的。所以如今他们想要寻找最短的从商店到赛场的路线。你能够帮助他们吗？

Input

输入包含多组数据。

每组数据第一行是两个整数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

//bellman_ford算法，求单源到其他节点的最短路。能够处理含有负权的边，而且能推断图中是否存在负权回路（这一条在一些题中也有应用）//无向图转化为有向图，边数加倍，构造边结构体，没用到邻接矩阵#include 
     
      using namespace std;const int maxNodeNum=110;//最多节点个数const int maxEdgeNum=10010;//最多边条数int nodeNum,edgeNum;//节点，有向边个数int dis[maxNodeNum];//从单源点到各个点的距离const int inf=0x3f3f3f3f;//边的权重无穷大数bool loop;//推断是否存在负权回路struct Edge{    int s,e,w;}edge[maxEdgeNum*2];//构造边，这里由于是无向图，要看成有向处理。void bellman_ford(int start){    //第一步：赋初值    for(int i=1;i<=nodeNum;i++)        dis[i]=inf;    dis[start]=0;    //第二步，对边进行松弛更新操作    for(int i=1;i<=nodeNum-1;i++)//最短路径为简单路径不可能含有环，图中最多有nodeNum-1条边    {        bool ok=0;        for(int j=1;j<=edgeNum;j++)        {            if(dis[edge[j].s]+edge[j].w
      
       >nodeNum>>edgeNum&&(nodeNum||edgeNum))    {        int from,to,w;        int cnt=1;        for(int i=1;i<=edgeNum;i++)//无向图，一条无向边看为两条有向边        {            cin>>from>>to>>w;            edge[cnt].s=edge[cnt+1].e=from;            edge[cnt].e=edge[cnt+1].s=to;            edge[cnt++].w=w;            edge[cnt++].w=w;//切记。不能写成 edge[cnt++]=edge[cnt++].w；        }        edgeNum*=2;//无向图        bellman_ford(1);        cout<
       
        <

//SPFA算法，是对bellman_ford算法的优化。採用队列，在队列中取点对其相邻的点进行松弛操作//假设松弛成功且相邻的点不在队列中，就把相邻的点增加队列，被取的点出队，并把它的状态(是否在队列中)//改为否。vis[i]=0,同一个节点能够多次进入队列进行松弛操作//这种题操作步骤：首先建立邻接矩阵。邻接矩阵初始化为inf,注意须要推断一下输入的边是否小于已有的边。取最小的那个，由于可能有重边,//建立完邻接矩阵，写SPFA函数，dis[]数组初始化为inf,源点dis[start]=0#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxNodeNum=110;//最多节点个数const int maxEdgeNum=10010;//最多边条数const int inf=0x3f3f3f3f;//边的权重无穷大数int nodeNum,edgeNum;//节点。有向边个数int dis[maxNodeNum];//从单源点到各个点的距离bool vis[maxNodeNum];//某个节点是否已经在队列中int mp[maxNodeNum][maxNodeNum];//建立邻接矩阵void SPFA(int start){    //第一步：建立队列。初始化vis,dis数组。并把源点增加队列中，改动其vis[]状态    queue
        
         q;    memset(vis,0,sizeof(vis));    for(int i=1;i<=nodeNum;i++)        dis[i]=inf;    dis[start]=0;    q.push(start);    vis[start]=1;    //第二步：在队列中取点，把其vis状态设为0，对该点相邻的点（连接二者的边）进行松弛操作，改动相邻点的dis[]    //并推断相邻的点vis[]状态是否为0(不存在于队列中),假设是。将其增加到队列中    while(!q.empty())    {        int from=q.front();        q.pop();        vis[from]=0;//别忘了这一句，哎        for(int i=1;i<=nodeNum;i++)        {            if(dis[from]+mp[from][i]
         
          >nodeNum>>edgeNum&&(nodeNum||edgeNum))    {        int from,to,w;        memset(mp,inf,sizeof(mp));//初始化        for(int i=1;i<=edgeNum;i++)//无向图，一条无向边看为两条有向边        {            cin>>from>>to>>w;            if(w

//floyed算法，时间复杂度高，但代码简单。能够处理负边，但图中不能包括负权回路//能够求随意一点到另外一点的最短路。而不仅仅是源点唯一#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxNodeNum=110;//最多节点个数const int maxEdgeNum=10010;//最多边条数const int inf=0x3f3f3f3f;int nodeNum,edgeNum;//节点，有向边个数int mp[maxNodeNum][maxNodeNum];//建立邻接矩阵void floyed(){    for(int k=1;k<=nodeNum;k++)        for(int i=1;i<=nodeNum;i++)            for(int j=1;j<=nodeNum;j++)                if(mp[i][k]+mp[k][j]
        
         >nodeNum>>edgeNum&&(nodeNum||edgeNum))    {        int from,to,w;        memset(mp,inf,sizeof(mp));//初始化        for(int i=1;i<=edgeNum;i++)//无向图，一条无向边看为两条有向边        {            cin>>from>>to>>w;            if(w

//dijkstra算法求最短路，单源最短路，不能处理带有负权的图//思想为单源点增加集合，更新dis[]数组。每次取dis[]最小的那个点。增加集合，再次更新dis[]数组，取点增加集合，直到全部的点都增加集合中#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxNodeNum=110;//最多节点个数const int maxEdgeNum=10010;//最多边条数const int inf=0x3f3f3f3f;int nodeNum,edgeNum;//节点，有向边个数int mp[maxNodeNum][maxNodeNum];//建立邻接矩阵int dis[maxNodeNum];//dis[i]为源点到i的最短路径bool vis[maxNodeNum];//推断某个节点是否已增加集合void dijkstra(int start){    //**第一步：初始化。dis[]为最大，vis均为0（都未增加集合）    memset(dis,inf,sizeof(dis));    memset(vis,0,sizeof(vis));    dis[start]=0;    //
        注意不能写vis[start]=1,由于这时候第一个节点还没有被訪问。以下循环中。第一个选择的就是第一个节点，切记    //**第二步：找dis[]值最小的点。增加集合，并更新与其相连的点的dis[]值        //一開始集合里没有不论什么点。以下的循环中，第一个找到的点肯定是源点    for(int i=1;i<=nodeNum;i++)    {        //寻找dis[]最小的点，增加集合中        int MinNumber,Min=inf;//MinNumber为dis[]值最小的点的编号        for(int j=1;j<=nodeNum;j++)        {            if(dis[j]
        
         >nodeNum>>edgeNum&&(nodeNum||edgeNum))    {        int from,to,w;        memset(mp,inf,sizeof(mp));//初始化        for(int i=1;i<=edgeNum;i++)//无向图，一条无向边看为两条有向边        {            cin>>from>>to>>w;            if(w

转载地址：http://ruicm.baihongyu.com/

你可能感兴趣的文章