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