[Usaco2009 Feb]Revamping Trails 堆优化 Dijkstra

这题一眼就看出就是一个二维DP
dp[i][j]表示到点i使用了j次免费边的最短距离


MD 卡SPFA。。
遂写dij。 AC


[cpp] view plaincopy
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define eps 1e-8  
#define MAXN 11111  
#define MAXM 111111  
#define INF 111111111  
using namespace std;  
typedef pair P;  
vector

g[MAXN];  
long long dis[MAXN][22];  
int n, m, k;  
struct node  
{  
    int v, num;  
    long long w;  
    node(){}  
    node(int a, int b, long long c){v = a; num = b; w = c;}  
    bool operator >(const node &cmp) const  
    {  
        return w > cmp.w;  
    }  
};  
priority_queue, greater > q;  
void dij()  
{  
    for(int i = 1; i <= n; i++)  
        for(int j = 0; j <= k; j++)  
            dis[i][j] = INF;  
    dis[1][0] = 0;  
    q.push(node(1, 0, 0));  
    while(!q.empty())  
    {  
        node tmp = q.top();  
        q.pop();  
        int u = tmp.v;  
        int num = tmp.num;  
        long long w = tmp.w;  
        for(int i = 0; i < g[u].size(); i++)  
        {  
            int v = g[u][i].first;  
            long long tw = g[u][i].second;  
            if(num < k && w < dis[v][num + 1])  
            {  
                dis[v][num + 1] = w;  
                q.push(node(v, num + 1, w));  
            }  
            if(w + tw < dis[v][num])  
            {  
                dis[v][num] = w + tw;  
                q.push(node(v, num, w + tw));  
            }  
        }  
    }  
    long long ans = dis[n][0];  
    for(int i = 1; i <= k; i++)  
        ans = min(ans, dis[n][i]);  
    printf("%lld\n", ans);  
}  
int main()  
{  
    int u, v, w;  
    while(scanf("%d%d%d", &n, &m, &k) != EOF)  
    {  
        while(!q.empty()) q.pop();  
        for(int i = 0; i <= n; i++) g[i].clear();  
        for(int i = 0; i < m; i++)  
        {  
            scanf("%d%d%d", &u, &v, &w);  
            g[u].push_back(make_pair(v, w));  
            g[v].push_back(make_pair(u, w));  
        }  
        dij();  
    }  
    return 0;  
}