计蒜客信息学8月普及组模拟赛C-DD去旅行

题目大意：n个点m条边，从1走到n需要多少代价？（边的代价为点数*距离）

最短路问题，只是需要记录每个点的深度，更新距离是需要用到。

每个点都有n种深度，很难确定SPFA的队列开多大，故用优先队列，当点n出队时，最小代价就出来了，因为后面的代价只会越来越大。

#include <bits/stdc++.h>
#define N 1005
#define LL long long
using namespace std;
LL n, m, i, j, k, a, b, c, v, s, mp[N][N], h[N];
struct AB{
    LL a, b, c, n;
} d[N*20];
struct AS{
    LL a, s, v;
    bool operator < (const AS &A) const{
        if(s != A.s) return s > A.s;
        return v > A.v;
    }
} t;
priority_queue <AS> q;
int main(){
    scanf("%lld%lld", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%lld%lld%lld", &a, &b, &c);
        d[i].a = a, d[i].b = b, d[i].c = c;
        d[i].n = h[a], h[a] = i;
    }
    memset(mp, 9, sizeof(mp));
    q.push((AS){1, mp[1][1]=0, 1});
    while(q.size()){
        t = q.top(), q.pop();
        a = t.a, s = t.s, v = t.v;
        if(a == n) break;
        if(v > n || s>mp[a][v]) continue;
        for(i=h[a]; i; i=d[i].n){
            b = d[i].b, c = d[i].c;
            if(s+v*c < mp[b][v+1]){
                mp[b][v+1] = s + v*c;
                q.push((AS){b, mp[b][v+1], v+1});
            }
        }
    }
    printf("%lld\n", s);
    return 0;
}

#include <bits/stdc++.h>
#define N 1005
#define LL long long
using namespace std;
LL mp[N][N], v, s, ans=1e18;
LL n, m, i, j, k, a, b, c, h[N];
struct AB{
    LL a, b, c, n;
} d[N*20], q[N*400];
int main(){
    scanf("%lld%lld", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%lld%lld%lld", &a, &b, &c);
        d[i].a = a, d[i].b = b, d[i].c = c;
        d[i].n = h[a], h[a] = i;
    }
    memset(mp, 9, sizeof(mp));
    q[1] = (AB){1, 1, mp[1][1]=0};
    for(i=j=1; i<=j; i++){
        a = q[i].a, s = q[i].c, v = q[i].b;
        if(j > n*400) break;
        for(k=h[a]; k; k=d[k].n){
            b = d[k].b, c = d[k].c;
            if(v<n && s+v*c < mp[b][v+1]){
                mp[b][v+1] = s + v*c;
                q[++j] = (AB){b, v+1, mp[b][v+1]};
            }
        }
    }
    for(i=1; i<=n; i++) ans = min(ans, mp[n][i]);
    printf("%lld\n", ans);
    return 0;
}

深搜部分分：

#include <bits/stdc++.h>
#define N 1005
#define LL long long
using namespace std;
LL mp[N][N], v, s, ans=1e18;
LL n, m, i, j, k, a, b, c, h[N];
struct AB{
    LL a, b, c, n;
} d[N*20];
void dfs(LL a, LL s, LL v){
    int b, c, i;
    if(a == n){
        ans = min(ans, s);
        return;
    }
    if(s >= mp[a][v]) return;
    mp[a][v] = s;
    for(i=1; i<v; i++){
        if(mp[a][i] < s) return;
    }
    for(i=h[a]; i; i=d[i].n){
        b = d[i].b, c = d[i].c;
        dfs(b, s+c*v, v+1);
    }
}
int main(){
    scanf("%lld%lld", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%lld%lld%lld", &a, &b, &c);
        d[i].a = a, d[i].b = b, d[i].c = c;
        d[i].n = h[a], h[a] = i;
    }
    memset(mp, 9, sizeof(mp));
    dfs(1, 0, 1);
    printf("%lld\n", ans);
    return 0;
}