---

layout: post

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

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- 最短路

- 基础DP

- Dijkstra

- 图论

- 训练指南

---

Walk Through the Forest UVA - 10917

题意

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

题意

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

#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;

}