感谢@wavator 提供解题思路!

题意:

n个点m条边的图

求1到n的最短路

PS:路径长度只计算路径上长度最大的k条边

n<=3000 m<=3000 k<=m

解法:

每次我们枚举最小值,然后做dijkstra

dijkstra的时候,我们让所有边的长度减t(负的按0计),最后答案再加t*k

这样,我们可以保证:

对于t是最小值,如果没走满k条边,那么答案肯定会更劣(因为我们多加了t*k,理论上应该是t*边数)

如果走满了k条边的话,如果是k条边以上,答案肯定没有最小值更大的优

所以这样就可以求得最小值

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long dist[3005];
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * new_edge()
{
    static edge a[6005];
    static int top=0;
    return &a[top++];
}
edge * li[3005];
void inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    t->weight=z;
    li[x]=t;
}
void insert_edge(int x,int y,int z)
{
    inserts(x,y,z);
    inserts(y,x,z);
}
int w[3005];
int k;
int n;
long long ans=1999999999999999999ll;
bool vis[3005];
void dijkstra(int w)
{
    memset(dist,-1,sizeof(dist));
    memset(vis,false,sizeof(vis));
    dist[0]=0;
    priority_queue<pair<long long,int> > q;
    q.push(make_pair(0,0));
    for (;!q.empty();)
    {
        int now=q.top().second;
        q.pop();
        if (vis[now]) continue;
        vis[now]=true;
        edge * t;
        for (t=li[now];t!=0;t=t->next)
        {
            if ((dist[t->y]==-1)||(dist[t->y]>dist[now]+max(0,t->weight-w)))
            {
                dist[t->y]=dist[now]+max(0,t->weight-w);
                q.push(make_pair(-dist[t->y],t->y));
            }
        }
    }
    if (dist[n-1]==-1) return;
    ans=min(ans,dist[n-1]+(long long)w*k);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int m;
    scanf("%d%d%d",&n,&m,&k);
    int i;
    for (i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d%d",&x,&y,&w[i]);
        x--;
        y--;
        insert_edge(x,y,w[i]);
    }
    dijkstra(0);
    for (i=0;i<m;i++)
    {
        dijkstra(w[i]);
    }
    cout<<ans<<endl;
    return 0;
}