[USACO09FEB]改造路题解

题目链接

今天机房模拟赛的题目，先用爆搜做的，后面去写了dijkstra（没想到过掉了）

本菜鸡之前并没有学过分层图，所以我感觉用的是dijkstra加动态规划的思想

我们用\(dis[i][j]\)来表示到从1号牧场到第\(i\)号牧场升级\(j\)条路所花的最短时间，设第\(x\)号牧场与第\(i\)号牧场相连通，\(road(i,x)\)表示\(i\)到\(x\)的路径长度，从\(i\)到\(x\)，要么升级路径，要么就不升级，那么不难发现

\(dis[x][j]=min(dis[i][j]+road(i,x),dis[x][j])\)

\(dis[x][j+1]=min(dis[i][j],dis[x][j+1])\)

接下来讲讲我的dijkstra，用\(k\)个堆来存最小的\(dis[i]\)，从不升级路径枚举到升级k条路径，下面是这一部分的代码

    for(int j=0; j<=k; j++)  //枚举升级路径的条数
    {
        memset(vis,0,sizeof(vis));
        while(!q[j].empty())
        {
            p=q[j].top();
            q[j].pop();
            if(vis[p.a]==0) //未访问过
            {
                vis[p.a]=1;
                for(int i=0; i<l[p.a].size(); i++)
                    if(vis[l[p.a][i]]==0)
                    {
                        son=l[p.a][i]; //与i相连的节点
                        if(p.sum+l1[p.a][i]<dis[son][j]) //不升级路径
                        {
                            dis[son][j]=p.sum+l1[p.a][i];
                            node txt;
                            txt.a=l[p.a][i],txt.sum=dis[son][j];
                            q[j].push(txt);
                        }
                        if(j!=k&&p.sum<dis[son][j+1]) //升级路径
                        {
                            dis[son][j+1]=p.sum;
                            node txt;
                            txt.a=l[p.a][i],txt.sum=dis[son][j+1];
                            q[j+1].push(txt);
                        }
                    }
            }
        }
    }

也没什么其他要讲的啦，接下来是全部代码

#include<bits/stdc++.h>
using namespace std;
#define int long long //注意要long long！！！ 
struct node
{
    int a,sum;
    bool operator<(const node&aaa)const
    {
        return aaa.sum<sum;
    }
} p;
int n,m,k,dis[10003][23],x,y,w,ans=1e9,vis[10003],son;
vector<int>l[10003],l1[10003]; //vector存图
priority_queue<node>q[23]; //用堆优化dijkstra 
signed main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        l[x].push_back(y),l[y].push_back(x),l1[x].push_back(w),l1[y].push_back(w); //存图
    }
    for(int i=1; i<=n; i++)
        for(int j=0; j<=k; j++)
            dis[i][j]=1e9; //记得赋初值
    dis[1][0]=0,p.a=1,p.sum=0;
    q[0].push(p);
    for(int j=0; j<=k; j++)  //枚举升级路径的条数
    {
        memset(vis,0,sizeof(vis));
        while(!q[j].empty())
        {
            p=q[j].top();
            q[j].pop();
            if(vis[p.a]==0) //未访问过
            {
                vis[p.a]=1;
                for(int i=0; i<l[p.a].size(); i++)
                    if(vis[l[p.a][i]]==0)
                    {
                        son=l[p.a][i]; //与i相连的节点
                        if(p.sum+l1[p.a][i]<dis[son][j]) //不升级路径
                        {
                            dis[son][j]=p.sum+l1[p.a][i];
                            node txt;
                            txt.a=l[p.a][i],txt.sum=dis[son][j];
                            q[j].push(txt);
                        }
                        if(j!=k&&p.sum<dis[son][j+1]) //升级路径
                        {
                            dis[son][j+1]=p.sum;
                            node txt;
                            txt.a=l[p.a][i],txt.sum=dis[son][j+1];
                            q[j+1].push(txt);
                        }
                    }
            }
        }
    }
    cout<<dis[n][min(m,k)];
    return 0;
}