训练指南 UVA - 10917（最短路Dijkstra + 基础DP）

Diposting di | Edited on

Walk Through the Forest

UVA - 10917

题意

Jimmy打算每天沿着一条不同的路走，而且，他只能沿着满足如下条件的道路（A，B）：存在一条从B出发回家的路径，比所以从A出发回家的路径都短，你的任务是计算有多少条不同的路径

题意

题意就转化成如果终点到i 比到j的路劲短，就连线，然后记忆化搜索就行（这几天这种题做太多次了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1050;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,u;
    bool operator <(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m;              ///点数和边数  点编号0~N-1
    vector<Edge>edges;    ///边列表
    vector<int>G[maxn];   ///每个节点出发的边编号
    bool done[maxn];      /// 是否已永久标号
    int d[maxn];          /// s到各个点的距离
    int p[maxn];          /// 最短路中的上一条边

    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int dist){ ///无向图调用两次
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s){
        priority_queue<HeapNode>Q;
        for(int i=0;i<n;i++)d[i]=inf;
        d[s]=0;
        memset(done,0,sizeof(done));
        Q.push((HeapNode){0,s});
        while(!Q.empty()){
            HeapNode x=Q.top();Q.pop();
            int u=x.u;
            if(done[u])continue;
            done[u]=true;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }
    /// dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括s和t）
    void GetShortestPaths(int s,int* dist,vector<int>* paths){///paths是二维链表
        dijkstra(s);
        for(int i=0;i<n;i++){
            dist[i]=d[i];
            paths[i].clear();
            int t=i;
            paths[i].push_back(t);
            while(t!=s){
                paths[i].push_back(edges[p[t]].from);
                t=edges[p[t]].from;
            }
            reverse(paths[i].begin(),paths[i].end());
        }
    }
};

Dijkstra solver;
int d[maxn];
int dp(int u){
    if(u==1)return 1;
    int &ans=d[u];
    if(ans>=0)return ans;
    ans=0;
    for(int i=0;i<solver.G[u].size();i++){
        int v=solver.edges[solver.G[u][i]].to;
        if(solver.d[v]<solver.d[u])ans+=dp(v);
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    while(cin>>n){
        if(n==0)break;
        cin>>m;
        solver.init(n);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;a--;b--;
            solver.AddEdge(a,b,c);
            solver.AddEdge(b,a,c);
        }
        solver.dijkstra(1);
        memset(d,-1,sizeof(d));
        cout<<dp(0)<<endl;
    }
    return 0;
}