最短路径 HDU2680

            <!-- wp:paragraph -->

这个是最短路专题的第一题,挺水的。

但是,一开始做的时候,没想到用逆向思维。

题目给出T(100)组数据,然后n(1000)个点,m条边(10000),然后有t次询问(t=1000)。询问某点到终点的最短距离。

太沙雕了,看见题目之后,第一反应就是,堆优化dijkstra,时间复杂度刚刚好。nlogn*t*T。。刚刚好被卡,但是没想那么多,直接扫描。也就是,直接邻接表,然后判重存图,然后优先队列啥的,枚举t次询问,每次询问都找一次,单源最短路。。。。。。

然后顺利RE了。红红火火恍恍惚惚。

后来看了一下题解,发现!!!好水啊,根本用不着堆优化dijkstra。直接逆向存图,普通邻接矩阵随便搞一下就出来了。

骄傲的是,重写之后,我的dijkstra一次写对,一次ac。

下面贴一个dijkstra板子

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
#define INF 0x7fffffff
void dijkstra(int n,int s,int *d)
{
    bool vis[n+1];
    for(int i=0;i<=n;i++) d[i]=INF,vis[i]=true;
    d[s]=0;
    for(int i=0;i<n;i++)
    {
        int index=-1;
        int maxx=INF;
        for(int j=1;j<=n;j++)
            if (vis[j]&&d[j]<maxx) index=j,maxx=d[j];
        if(index==-1) break;
        vis[index]=false;
        for(int i=1;i<=n;i++)
        {
            if(a[index][i]!=INF&&d[index]+a[index][i]<d[i]) d[i]=d[index]+a[index][i];
        }
    }
    //for(int i=1;i<=n;i++)
    //  cout<<d[i]<<" ";
    //cout<<endl;
}
int main()
{
    int n,m,s,k;
    while(scanf("%d%d%d",&n,&m,&s)==3)
    {   
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                if(i!=j) a[i][j]=INF;else a[i][j]=0;
        for(int i=0;i<m;i++)
        {
            int x1,x2,x3;
            scanf("%d%d%d",&x1,&x2,&x3);
            if(a[x2][x1]>x3) a[x2][x1]=x3;
        }
        int d[n+1];
        dijkstra(n,s,d);
        scanf("%d",&k);
        int ans=INF;
        for(int i=0;i<k;i++)
        {
            int x;
            scanf("%d",&x);
            ans=min(ans,d[x]);
        }
        if(ans==INF) cout<<-1<<endl;else cout<<ans<<endl;
    }
    return 0;
} 

您可能还喜欢...

1 条回复

  1. 苏源说道:

    感谢大佬!!!

发表评论

电子邮件地址不会被公开。 必填项已用*标注