dij+堆优化+O2 60分TLE四个点
查看原帖
dij+堆优化+O2 60分TLE四个点
320697
AMIRIOX無暝楼主2021/1/14 11:11

想不出还有哪里可以卡的了/kel

#include <iostream>
#include <cstdio>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
const int maxn = 50000;
const int maxm = 100000*2;
int vis[maxn], dis[maxn];
typedef pair<int, int> P;
struct edge
{
    int to, w, nxt;
    edge() { nxt = -1; }
} g[maxm];
int tot, head[maxn];
void addEdge(int u, int to, int w)
{
    g[++tot].to = to;
    g[tot].w = w;
    g[tot].nxt = head[u];
    head[u] = tot;
}
struct node
{
    int u, dis;
    node(int _u, int _dis) : u(_u), dis(_dis) {}
    bool operator<(const node &o) const
    {
        return this->dis > o.dis;
    }
};
P dijkstra(int s, int e)
{
    priority_queue<node> q;
    q.push(node(1, 0));
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    while (!q.empty())
    {
        node x = q.top();
        q.pop();
        if (vis[x.u])
            continue;
        vis[x.u] = 1;
        for (int i = head[x.u]; ~i; i = g[i].nxt)
        {
            int y = g[i].to;
            if (dis[y] > dis[x.u] + g[i].w)
                dis[y] = dis[x.u] + g[i].w;
            if (!vis[y])
                q.push(node(y, dis[y]));
        }
    }
    return P(dis[s],dis[e]);
}
int main(void)
{
    int n, m, b;
    scanf("%d %d %d", &n, &m, &b);
    for (int i = 1; i <= n; i++)
        head[i] = -1;
    // printf("n,m,b input ok\n");
    for (int i = 1; i <= m; i++)
    {
        int x, y, v;
        scanf("%d %d %d", &x, &y, &v);
        addEdge(x, y, v);
        addEdge(y, x, v);
    }
    // printf("edges input ok\n");
    for (int i = 1; i <= b; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        int ax,ay;
        tie(ax,ay)=dijkstra(x, y);
        printf("%d\n", ax+ay);
    }
    return 0;
}
2021/1/14 11:11
加载中...