UVa 10917 Dijkstra

本来就是水题一道。

题意：一个人要从点1去到点2，中间还有很多点和很多条边。问你如果他每次走的边(a,b)都满足：a点到目标点的最短距离<b点到目标点的最短距离，那么他从点1出发到点2总共有多少条路径。

思路：先用Dijkstra求最短路，然后创一个图，对于满足条件的边(a,b)就加一条有向边，由于是严格按照小于加的边，图中绝对没有环，是个DAG。接下来dp就行了。

dp[i]表示i点出发有多少条路径，dp[i]=sum(dp[j])。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <queue>
 5 using namespace std;
 6 const int maxn=1005;
 7 const int INF=0x3f3f3f3f;
 8 struct Edge{
 9     int from,to,dist;
10 };
11 struct HeapNode{
12     int d,u;
13     bool operator < (const HeapNode& rhs) const
14     {
15         return d>rhs.d;
16     }
17 };
18 struct Dijkstra{
19     int n,m;
20     int d[maxn],p[maxn];
21     bool done[maxn];
22     vector<Edge> edges;
23     vector<int> G[maxn];
24     void init(int n)
25     {
26         this->n=n;
27         for(int i=0;i<n;i++)G[i].clear();
28         edges.clear();
29     }
30     void AddEdge(int from,int to,int dist)
31     {
32         edges.push_back((Edge){from,to,dist});
33         m=edges.size();
34         G[from].push_back(m-1);
35     }
36     void dijkstra(int s)
37     {
38         priority_queue<HeapNode> Q;
39         int u;
40         HeapNode x;
41         for(int i=0;i<n;i++)d[i]=INF;
42         d[s]=0;
43         memset(done,0,sizeof(done));
44         Q.push((HeapNode){0,s});
45         while(!Q.empty()){
46             x=Q.top();Q.pop();
47             u=x.u;
48             if(done[u])continue;
49             done[u]=true;
50             for(int i=0;i<G[u].size();i++){
51             Edge& e=edges[G[u][i]];
52                 if(d[e.to] > d[e.from]+e.dist){
53                     d[e.to]=d[e.from]+e.dist;
54                     p[e.to]=G[u][i];
55                     Q.push((HeapNode){d[e.to],e.to});
56                 }
57             }
58         }
59     }
60 };
61 int n;
62 Dijkstra solver;
63 vector<int> Map[maxn];
64 int dp[maxn];
65 int dfs(int u)
66 {
67     if(dp[u]!=-1) return dp[u];
68     if(u==1) return dp[u]=1;
69     int ret=0;
70     for(int i=0;i<Map[u].size();i++)
71         ret+=dfs(Map[u][i]);
72     return dp[u]=ret;
73 }
74 
75 int main()
76 {
77     int m,a,b,c;
78     while(~scanf("%d%d",&n,&m)&&n){
79         solver.init(n);
80         while(m--){
81             scanf("%d%d%d",&a,&b,&c);
82             a--;b--;
83             solver.AddEdge(a,b,c);
84             solver.AddEdge(b,a,c);
85         }
86         solver.dijkstra(1);
87         for(int i=0;i<n;i++)Map[i].clear();
88         for(int i=0;i<solver.m;i++){
89             int &u=solver.edges[i].from;
90             int &v=solver.edges[i].to;
91             if(solver.d[u]>solver.d[v]) Map[u].push_back(v);
92         }
93         memset(dp,-1,sizeof(dp));
94         printf("%d
",dfs(0));
95     }
96     return 0;
97 }