8006 Connections

https://www.acmicpc.net/problem/8006

K번째 최단경로 찾기와 같은 문제인데 쿼리로 최대 10000개가 들어오므로 매번 구한다면 시간 초과가 난다.

D[S][E][K] = S에서 E로 가는 K번째 최단경로의 길이라고 하고 미리 쿼리를 다 구해놓고 각 쿼리마다 D 배열값을 출력해준다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int n,m,a,b,c,q,s,e,k;
int d[101][101][101];
vector<pair<int,int>> adj[105];
 
void dijkstra()
{
    priority_queue<int> path[101];
    priority_queue<pair<int,int>> pq;
    pq.push({0,s});
 
    while(!pq.empty())
    {
        int cost=-pq.top().first;
        int now=pq.top().second;
        pq.pop();
 
        for(auto i : adj[now])
        {
            int next=i.first;
            int ndist=i.second+cost;
 
            if(path[next].size()<k)
            {
                path[next].push(ndist);
                pq.push({-ndist,next});
            }
            else if(path[next].top()>ndist)
            {
                path[next].pop();
                path[next].push(ndist);
                pq.push({-ndist,next});
            }
        }
    }
 
    for(int e=1;e<=n;e++)
        for(int k=path[e].size();k>=1;k--)
            d[s][e][k]=path[e].top(),path[e].pop();
}
 
int main()
{
    scanf("%d %d",&n,&m);
    while(m--)
    {
        scanf("%d %d %d",&a,&b,&c);
        adj[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++)
    {
        s=i,k=100;
        dijkstra();
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d %d %d",&s,&e,&k);
        printf("%d\n",d[s][e][k]?d[s][e][k]:-1);
    }
    return 0;
}