bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级优先队列+dij

1579: [Usaco2009 Feb]Revamping Trails 道路升级

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1768 Solved: 481
[Submit][Status][Discuss]

Description

每天,农夫John需要经过一些道路去检查牛棚N里面的牛. 农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M. 道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N). John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i 走到P１_i 他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K (1 <= K <= 20)条路经，将它们所须时间减为０．帮助FJ选择哪些路经需要更新使得从１到N的时间尽量少.

Input

* 第一行: 三个空格分开的数: N, M, 和 K * 第2..M+1行: 第i+1行有三个空格分开的数：P1_i, P2_i, 和 T_i

Output

* 第一行: 更新最多Ｋ条路经后的最短路经长度．

Sample Input

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Sample Output

HINT

K是1; 更新道路3->4使得从３到４的时间由１００减少到０. 最新最短路经是1->3->4,总用时为１单位. N<=10000

思路：dp；

　　　dp[i][j]表示从1-i使用了更新j次的最少距离；

　　　dp[v][j]=min(dp[i][j]+w,dp[i][j-1]);

　　　加一维求最短路，优先队列优化；

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define pi (4*atan(1.0))
const int N=1e5+10,M=4e6+10,inf=1e9+10;
const ll INF=1e18+10;
struct is
{
    int v,w;
    int next;
}edge[N*4];
int head[N*4],si;
int flag[N][23];
int d[N][23];
struct point
{
    int pos,dis;
    point(int a,int b){pos=b;dis=a;}
    friend bool operator <(point x,point y)
    {
        return x.dis>y.dis;
    }
};
void add(int u,int v,int w)
{
    si++;
    edge[si].v=v;
    edge[si].w=w;
    edge[si].next=head[u];
    head[u]=si;
}
void dij(int n,int k)
{
    priority_queue<point>q;
    point a(0,1);
    q.push(a);
    while(!q.empty())
    {
        point v=q.top();
        q.pop();
        int x=(v.pos)%(n+1);
        int y=(v.pos)/(n+1);
        if(flag[x][y])continue;
        flag[x][y]=1;
        for(int i=head[x];i;i=edge[i].next)
        {
            int vv=edge[i].v;
            if(d[vv][y]>d[x][y]+edge[i].w)
            {
                d[vv][y]=d[x][y]+edge[i].w;
                q.push(point(d[vv][y],y*(n+1)+vv));
            }
            if(y==k)continue;
            if(d[vv][y+1]>d[x][y])
            {
                d[vv][y+1]=d[x][y];
                q.push(point(d[vv][y+1],(y+1)*(n+1)+vv));
            }
        }
    }
    printf("%d
",d[n][k]);
}
void init()
{
    si=0;
    memset(head,0,sizeof(head));
    memset(flag,0,sizeof(flag));
    for(int i=1;i<N;i++)
    for(int t=0;t<21;t++)
    d[i][t]=inf;
    d[1][0]=0;
}
int main()
{
    int x,y,z,i,t;
    while(~scanf("%d%d%d",&x,&y,&z))
    {
        init();
        for(i=0;i<y;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        dij(x,z);
    }
    return 0;
}