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

HDU 5521 Meeting【最短路】

程序员文章站 2022-05-22 14:32:45
...

今天旁观了Angry_Newbie的模拟区域赛(2015shenyang)
倒着看最先看的M题,很明显的最短路问题,在我看懂的时候他们已经开始敲B了。
后来听说D过了很多人。。
D题一看是个博弈,给了很多组样例,找找规律懵一懵就ac了。然后我就滚粗了。。。
而他们也早就A了D,很快他们又A了B。。。
后来就全程看着罗大神敲无限TLE的M。感觉算法肯定没错,但是想不到哪里还可以优化。
后来我滚了之后听说他们也成功AC了M。

下来仔细想想M也并不是难题,如果平时做的话,肯定不会卡那么久的。。。


A REALLY LONG WAY TO GO


题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5521

题意:

有n个块,m个块集,每个块集中的块相连且之间的距离相等,一个人在1号块,另一个人在n号块,求两人同时出发,在哪个块会面两人走的距离最小?

分析:

两头开始走的,直接求两次dijkstra。
在更新每块的时候更新该块所在块集中的其他点的距离。
但是边很多,有很多无用的边,当时一直在纠结如何处理那些无用的边。
但是,仔细想想,dijkstra的思想就是利用已经求出最短距离的点,求出与之相邻的点的距离。而对于每块而言,如果已经更新过该块集,那块集中的所有点目前为止已经处于最短路状态,无需再次对该块集进行更新了, 即每个块集最多松弛一次。。这样就避免了块集无用的重复访问。。大大优化。。

代码:

#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
#define INF 1e15
ll dist[maxn][2];
int vis[maxn];
vector<int>block[maxn];
vector<int>lable[maxn];
int n, m;
int t[maxn];
typedef pair<int, long long>p;
void dijkstra(int s, int flag)
{
    for(int i = 1; i <= n; i++) dist[i][flag] = INF;
    memset(vis, 0, sizeof(vis));
    priority_queue<p,vector<p>, greater<p> >q;
    q.push(p(0, s));
    dist[s][flag] = 0;
    while(!q.empty()){
        p tt = q.top();q.pop();
        int v = tt.second;
        if(dist[v][flag] < tt.first) continue;
        for(int i = 0; i < block[v].size(); i++){
            int a = block[v][i];
            if(vis[a]) continue;
            vis[a] = 1;
            for(int j = 0 ; j < lable[a].size(); j++){
                if(lable[a][j] == v) continue;
                int u = lable[a][j];
                if(dist[u][flag] > dist[v][flag] + t[a]){
                    dist[u][flag] = dist[v][flag] + t[a];
                    q.push(p(dist[u][flag], u));
                }
            }
        }
    }
}
int main (void)
{
    int T;scanf("%d", &T);
    int cnt = 1;
    while(T--){
        scanf("%d%d", &n, &m);
        int s, a;
        for(int i = 1; i <= n; i++)
            block[i].clear();
        for(int i = 1; i <= m; i++){
            lable[i].clear();
        }
        for(int i = 1; i <= m; i++){
            scanf("%d%d", &t[i], &s);
            for(int j = 0; j < s; j++){
                scanf("%d", &a);
                block[a].push_back(i);
                lable[i].push_back(a);
             }
        }
        dijkstra(1, 0);
        dijkstra(n, 1);
        ll ans = INF;
        for(int i = 1; i <= n; i++)
            ans = min(ans, max(dist[i][0], dist[i][1]));

        vector<int>v;
        printf("Case #%d: ", cnt++);
        if(ans == INF) printf("Evil John\n");
        else{
            printf("%I64d\n", ans);
            for(int i = 1; i <= n; i++){
                if(ans == max(dist[i][0], dist[i][1])){
                    v.push_back(i);
                }
            }
            for(int i = 0; i < v.size(); i++){
                printf("%d%c", v[i], i == v.size() - 1?'\n':' ');
            }
        }
    }
    return 0;
}