UESTC 30.最短路-最短路(Floyd or Spfa(链式前向星存图))

时间：2021-12-17 14:56:29

最短路

Time Limit: 3000/1000MS (Java/Others)
Memory Limit: 65535/65535KB (Java/Others)

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的T-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。

每组数据第一行是两个整数NN ,MM (N≤100N≤100 ,M≤10000M≤10000 )，NN 表示成都的大街上有几个路口，标号为11 的路口是商店所在地，标号为NN 的路口是赛场所在地，MM 则表示在成都有几条路。N=M=0N=M=0 表示输入结束。

接下来MM 行，每行包括33 个整数AA ,BB ,CC (1≤A1≤A ,B≤NB≤N ,1≤C≤10001≤C≤1000 ),表示在路口AA 与路口BB 之间有一条路，我们的工作人员需要CC 分钟的时间走过这条路。

输入保证至少存在11 条商店到赛场的路线。

Output

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

Sample input and output

Sample Input Sample Output 
2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0
 
3

2
 

题意好理解，就是最短路。

最短路。。。传送门http://developer.51cto.com/art/201403/433874.htm

打训练赛的时候这个题wa了7次，最后也没写对，也是没谁了(；´д｀)ゞ

代码:

#include<bits/stdc++.h>

using namespace std;

const int N=+;

const int INF=0x3f3f3f3f;

typedef long long ll;

int hh[N][N];

int n,m;

int gg(){                                                    //关键

    for(int h=;h<=n;h++)

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)                                   //这里当时写错了，j<=n写成j<=m了。。。

    hh[i][j]=min(hh[i][j],hh[i][h]+hh[h][j]);

}

int main(){

    int h,k,l;

    while(~scanf("%d%d",&n,&m)&&(n||m)){

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

            hh[i][j]=INF;

            for(int i=;i<m;i++){

                scanf("%d%d%d",&h,&k,&l);

                if(l<hh[h][k])

                    hh[h][k]=hh[k][h]=l;

            }

            gg();

            printf("%d\n",hh[][n]);

    }

    return ;

}

啊啊啊啊啊啊啊，还有一个思路可以写，spfa算法+链式前向星建图

然而，前向星有的看懂了，有的还很(O_O)?传送门http://www.cnblogs.com/Tovi/p/6194786.html

人家的代码，传送门http://blog.csdn.net/lvshubao1314/article/details/23034601

代码:

#include<string.h>

#include<stdio.h>

#include<iostream>

#include<queue>

using namespace std;

const int maxn=1e5+;

const int INF=1e9;

struct node{

    int b,w,next;

};

node edge[maxn];

int s,n,ip;

int head[maxn],que[maxn],visit[maxn],dis[maxn];

void add(int u,int v,int c){

    edge[ip].b=v;edge[ip].w=c;edge[ip].next=head[u];head[u]=ip++;

}

void spfa(int start,int numpoint){

    memset(visit,,sizeof(visit));

    for(int i=;i<=numpoint;i++)

        dis[i]=INF;

    int front=-,tail=-;

    dis[start]=;visit[start]=;que[++tail]=start;

    int top,to,temp;

    while(front!=tail){

        if(++front>numpoint)front-=numpoint;

        top=que[front];visit[top]=;

        for(int p=head[top];p!=-;p=edge[p].next){

            to=edge[p].b;temp=dis[top]+edge[p].w;

            if(dis[to]>temp){

                dis[to]=temp;

                if(!visit[to]){

                    if(++tail>numpoint)tail-=numpoint;

                    que[tail]=to;

                    visit[to]=;

                }

            }

        }

    }

}

int main(){

    int b,w,m,k;

    while(~scanf("%d%d",&n,&m)){

        if(m==&&n==)break;

        int maxx=-;

        memset(head,-,sizeof(head));

        ip=;

        for(int i=;i<=m;i++){

            cin>>k>>b>>w;

            if(k>maxx)maxx=k;

            if(b>maxx)maxx=b;

            add(k,b,w);

            add(b,k,w);

        }

        spfa(,maxx);

        printf("%d\n",dis[n]);

    }

    return ;

}

菜的掉渣，继续努力TAT

 

相关文章