[Solution][Graph Theory][Dijkstra]JLOI2011 飞行路线

【题目】

戳这里

【题意】

自行脑补。

【做法】

建立k+1层的层次图,每一层上都与原图相同。
另外对于每一条边,从连接上层的一端到下层的另一端。
原点为第0层的s,答案为第0~k层的t点的dis[]最小值。

【代码】(使用手写小根堆Dijkstra算法实现)

#include<cstdio>
#include<cctype>
#include<cstring>
inline int getc()
{
    static const int Len = 4096;
    static char buf[Len] , *S = buf , *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf , 1 , Len , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint()
{
    static char c;
    while(!isdigit(c = getchar()));
    int tmp = c - '0';
    while(isdigit(c = getchar()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
int head[200001] , end[2500001] , next[2500001] , len[2500001] , ind = 0;
void addedge(int a , int b , int _len)
{
    int q = ++ind;
    end[q] = b;
    len[q] = _len;
    next[q] = head[a];
    head[a] = q;
}
int n , m , k;
inline int hash(int level , int num)
{
    return level * n + num;
}
struct Node
{
    int num , dis;
    Node(int _num = 0, int _dis = 0):num(_num),dis(_dis){}
    bool operator < (const Node &T_Node) const
    {
        return dis < T_Node.dis;
    }
};
int save[200001];
struct Heap
{
    Node H[200001];
    int size , ins , minins;
    Node tmp;
    void insert(Node p)
    {
        H[++size] = p;
        save[p.num] = size;
        ins = size;
        while(ins != 1 && H[ins] < H[ins >> 1])
        {
            save[H[ins].num] = ins>>1;
            save[H[ins>>1].num] = ins;
            tmp = H[ins];
            H[ins] = H[ins >> 1];
            H[ins >> 1] = tmp;
            ins >>= 1;
        }
    }
    Node top()
    {
        return H[1];
    }
    void pop()
    {
        H[1] = H[size--];
        ins = 1;
        while((ins << 1) <= size)
        {
            minins = (((ins<<1)+1)<=size&&H[(ins<<1)+1]<H[ins<<1]) ? (ins<<1)+1 : (ins<<1);
            if (H[minins] < H[ins])
            {
                save[H[ins].num] = minins;
                save[H[minins].num] = ins;
                tmp = H[ins];
                H[ins] = H[minins];
                H[minins] = tmp;
                ins = minins;
            }
            else
                break;
        }
    }
    void change(int x , int newnum)
    {
        H[save[x]].dis = newnum;
        ins = save[x];
        while(ins != 1 && H[ins] < H[ins >> 1])
        {
            save[H[ins].num] = ins>>1;
            save[H[ins>>1].num] = ins;
            tmp = H[ins];
            H[ins] = H[ins>>1];
            H[ins>>1] = tmp;
            ins >>= 1;
        }
    }
}Q;
int dis[200001];
bool in[200001];
int s , t;
void Dijkstra()
{
    memset(dis , 0x3f , sizeof(dis));
    dis[hash(0 , s)] = 0;
    int i , j;
    for(i = 1 ; i <= (k + 1)*n ; ++i)
        Q.insert(Node(i , dis[i]));
    for(i = 1 ; i <= (k + 1)*n ; ++i)
    {
        while(in[Q.top().num])
            Q.pop();
        int now = Q.top().num;
        in[now] = 1;
        for(j = head[now] ; j ; j = next[j])
        {
            if (dis[end[j]] > dis[now] + len[j])
            {
                dis[end[j]] = dis[now] + len[j];
                Q.change(end[j] , dis[end[j]]);
            }
        }
    }
}
int main()
{
    n = getint() , m = getint() , k = getint();
    s = getint() , t = getint();
    s++ , t++;
    register int i , j;
    int a , b , x;
    for(i = 1 ; i <= m ; ++i)
    {
        a = getint() , b = getint() , x = getint();
        a++ , b++;
        for(j = 0 ; j <= k ; ++j)
        {
            addedge(hash(j , a) , hash(j , b) , x);
            addedge(hash(j , b) , hash(j , a) , x);
        }
        for(j = 0 ; j < k ; ++j)
        {
            addedge(hash(j , a) , hash(j + 1 , b) , 0);
            addedge(hash(j , b) , hash(j + 1 , a) , 0);
        }
    }
    Dijkstra();
    int mindis = 1 << 30;
    for(i = 0 ; i <= k ; ++i)
        if (dis[hash(i , t)] < mindis)
            mindis = dis[hash(i , t)];
    printf("%d" , mindis);
    return 0;
}
comments powered by Disqus