欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu5521最短路(Dijkstra)

程序员文章站 2022-05-22 14:33:03
...

题意:A和B两人要约会,A在!,B在N,给定M个集合,每个集合中,一个地方到另一个地方的花费一样,求花费最小是多少,还有他们在哪个地方约会,如果符合条件的有多个,按升序输出。

思路:第一印象是最短路,但在当时写时候直接暴力加边,是O(n^2)的算法,一直超时。

==》解决办法:每个集合都加一条边,然后集合内的每个点到这个点的距离都是x/2,当然,集合中任意两个点的距离还是x/2+x/2=x,这样如果一个集合有n个点,那么原来不优化的思路需要加n*(n-1)条边,优化之后只需加n条边,大大降低了时间复杂度。

另一个点,就是建图定时候,不再是n*n的图了,而是(n+m)*(n+m)的图了,所以在初始化的时候,就要写memset(vec,0,(n+m)*1)了;当时我只是一直初始化1-n,所以一直AC不了。

    1.点数N=n+2*最大集合数=1e5+2e6 
    2.边数M=3*最大集合数=3e6 
    3.要用LL存t和dist
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

typedef long long LL;
int n,m;
vector <int> ans;
const LL INF = 0x3f3f3f3f3f;
const int MAXN = 3200010;
struct qnode
{
    int v;
    LL c;
    qnode (int _v = 0, LL _c = 0) : v(_v), c(_c) {}
    bool operator < (const qnode &r) const { return c > r.c; }
};
struct Edge
{
    int v;
    LL cost;
    Edge (int _v = 0,LL _cost = 0) : v(_v), cost (_cost){}
};
vector <Edge> E[MAXN];
bool vis[MAXN];
LL dist[2][MAXN];
void dijkstra(int n,int start,int poi) //点从编号1开始
{
    memset(vis,0,sizeof(vis));
    for (int i = 1; i <= MAXN; i++) dist[poi][i] = INF;
    priority_queue <qnode> que;
    while(!que.empty()) que.pop();
    dist[poi][start] = 0;
    que.push(qnode(start,0));
    qnode tmp;
    while(!que.empty())
    {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < E[u].size(); i++)
        {
            int v = E[tmp.v][i].v;
            LL cost = E[u][i].cost;
            if (!vis[v] && dist[poi][v] > dist[poi][u] + cost)
            {
                dist[poi][v] = dist[poi][u] + cost;
                que.push(qnode(v,dist[poi][v]));
            }
        }
    }
}
void addedge(int u,int v,LL w)
{
    E[u].push_back(Edge(v,w));
}

int main(){
    int T;
    cin >> T;
    int cas = 1;
    while(T--)
    {
        for (int i = 0; i < MAXN; i++)
        {
            E[i].clear();
        }
        scanf("%d%d",&n,&m);
        int pos = n;    //用于记录新创建的点
        while(m--)
        {
            LL t;
            int s;
            scanf("%lld%d",&t,&s);
            pos++;
            while(s--)
            {
                int u;
                scanf("%d",&u);
                addedge(u,pos,t);
                addedge(pos,u,t);
            }
        }
        dijkstra(pos,1,0);  //从1出发,结果保存在dist[0][]中
        dijkstra(pos,n,1); //从n出发,结果保存在dist[1][]中
        LL mindis = INF;
        ans.clear();
        for (int i = 1; i <= n; i++)
        {
            mindis = min(mindis,max(dist[0][i],dist[1][i]));
        }
        if (mindis == INF) printf("Case #%d: Evil John\n",cas++);
        else
        {
            printf("Case #%d: %lld\n",cas++,mindis / 2);
            for (int i = 1; i <= n; i++)
            {
                if (mindis == max(dist[0][i],dist[1][i]))
                {
                    ans.push_back(i);
                }
            }
            printf("%d",ans[0]);
            for (int i = 1; i < ans.size(); i++)
            {
                printf(" %d",ans[i]);
            }
            printf("\n");
        }
    }
    return 0;
}

/*
 2
 5 4
 1 3 1 2 3
 2 2 3 4
 10 2 1 5
 3 3 3 4 5
 3 1
 1 2 1 2
*/