【题解】洛谷P2829

题目传送门

这道题和P2865一样，都是最短路。

只是在读入时统计度数，更新时增加判断：

if(v!=1&&v!=n&&deg[v]<k)continue;

这道题就过了。

文章最短的一次……

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5010,inf=0x3f3f3f3f;
struct edge
{
    int v,w;
};
vector <edge> g[MAXN];
struct node
{
    int u,dis;
    bool operator <(const node a)const 
    {
        return dis>a.dis;
    }
};
int dis[MAXN],ldis[MAXN],deg[MAXN],n,m,k;
bool vis[MAXN][MAXN];
priority_queue <node> q;
void dijkstra()
{
    memset(dis,inf,sizeof(dis));
    memset(ldis,inf,sizeof(ldis));
    dis[1]=0;
    q.push({1,0});
    while(!q.empty())
    {
        node front=q.top();
        q.pop();
        int u=front.u;
        if(front.dis>ldis[u]) continue;
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i].v,w=g[u][i].w;
            if(v!=1&&v!=n&&deg[v]<k)continue;//这里增加判断！！！
            if(front.dis+w<dis[v])
            {
                ldis[v]=dis[v];
                dis[v]=front.dis+w;
                q.push({v,dis[v]});
            }
            else if(front.dis+w>dis[v]&&front.dis+w<ldis[v])
            {
                ldis[v]=front.dis+w;
                q.push({v,ldis[v]});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        if(!vis[u][v])
        {//这里统计度数
            //vis记录这个边是否有记录过，防止重边
            vis[u][v]=vis[v][u]=1;
            deg[u]++,deg[v]++;
        }
    }
    dijkstra();
    if(ldis[n]==inf)cout<<-1;
    else cout<<ldis[n];
    return 0;
}