当前位置:网站首页>最短路

最短路

2021-07-20 12:14:01 软件工程小施同学

  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
 

  最最最简单的最短路问题!写了三个常用求最短路的算法:floyd、djikstra、spfa,都能轻松解决!


#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
const int N = 105;
const int INF = 99999999;
int map[N][N], dist[N];
bool visit[N];
int n, m;
void init()     //初始化
{
    int i, j;
    for(i = 1; i < N; i++)
    {
        for(j = 1; j < N; j++)
        {
            if(i == j) map[i][j] = 0;
            else map[i][j] = map[j][i] = INF;
        }
    }
}
void input()    //输入函数
{
    int vi, vj, cost;
    while(m--)
    {
        scanf("%d %d %d", &vi, &vj, &cost);
        if(cost < map[vi][vj])
            map[vi][vj] = map[vj][vi] = cost;
    }
}
void floyd()    //Floyd算法
{
    int i, j, k;
    for(k = 1; k <= n; k++)     //k为中间点
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(map[i][k] + map[k][j] <  map[i][j])
                     map[i][j] = map[i][k] + map[k][j];
}
void dijk()     //Dijkstra算法
{
    int i, j, next, MIN;
    memset(visit, false, sizeof(visit));
    for(i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;
    for(i = 1; i <= n; i++)
    {
        MIN = INF;
        for(j = 1; j <= n; j++)
            if(!visit[j] && dist[j] <= MIN)
                MIN = dist[next=j];
        if(MIN == INF) break;
        visit[next] = true;            //这里的visit用于表示该点是否在已处理点集中
        for(j = 1; j <= n; j++)
            if(!visit[j] && dist[j] > dist[next] + map[next][j])
                dist[j] = dist[next] + map[next][j];
    }
}
void spfa()     //SPFA算法
{
    int i, now;
    memset(visit, false, sizeof(visit));
    for(i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;
    queue<int> Q;
    Q.push(1);
    visit[1] = true;
    while(!Q.empty())
    {
        now = Q.front();
        Q.pop();
        visit[now] = false;
        for(i = 1; i <= n; i++)
        {
            if(dist[i] > dist[now] + map[now][i])
            {
                dist[i] = dist[now] + map[now][i];
                if(visit[i] == 0)
                {
                    Q.push(i);
                    visit[i] = true;    //这里的visit用于表示是否在队列中
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d %d", &n, &m))
    {
        if(!n || !m) break;
        init();
        input();
        //floyd();
        //dijk();
        spfa();
        //printf("%d\n", map[1][n]);
        printf("%d\n", dist[n]);
    }
    return 0;
}
      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.
  • 82.
  • 83.
  • 84.
  • 85.
  • 86.
  • 87.
  • 88.
  • 89.
  • 90.
  • 91.
  • 92.
  • 93.
  • 94.
  • 95.
  • 96.
  • 97.
  • 98.
  • 99.
  • 100.
  • 101.
  • 102.
  • 103.


版权声明
本文为[软件工程小施同学]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15077160/2915331