热爱互联网

hdu 1142 (最短路 + 记忆化搜索)

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1142

题意:有1~n共n个点.其中起点是标号为1的点,终点是标号为2的点.选择从点A到点B的路径的唯一条件就是:点B到达终点的距离比点A到终点的距离短.
从点1出发,每次只能选择比当前点更接近点2的点移动,问一共有多少种走法..

用最短路径算法求到点2的dis数组(以2为始点),然后记忆化搜索即可。

我是用spfa算法:

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
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int inf=0x3fffffff,MM=1005;
struct Edge{
       int v,to;
};
vector<edge>edge[MM];
queue<int>que;
int dis[MM],cnt[MM],vis[MM],V,E;
bool spfa(const int st){
     for(int i=1;i<=V;i++)
         dis[i]= ( i==st ? 0 : inf);
     memset(cnt,0,sizeof(cnt));
     memset(vis,0,sizeof(vis));
     que.push(st);
     vis[st]=1;
     cnt[st]=1;
     while(!que.empty()){
          int temp=que.front();
          vis[temp]=0;
          for(int i=0;i<edge[temp].size();i++){
              Edge *t=&edge[temp][i];
              if(dis[temp]+t->v<dis[t->to]){
                   dis[t->to]=dis[temp]+t->v;
                   if(!vis[t->to]){
                        que.push(t->to);
                        vis[t->to]=1;
                        cnt[t->to]++;
                        if(cnt[t->to]>V)
                            return false;
                   }
              }
          }
          que.pop();
     }
     return true;
}
/////////////////////////
int num[MM]; //num[i]存储点i到终点2的符合题意的路径数
int dfs(int v){
    if(num[v])
        return num[v];
    if(v==2)
        return 1;
    int sum=0;
    for(int i=0;i<edge[v].size();i++){
        int w=edge[v][i].to;
        if(dis[w]<dis[v]){
            sum+=dfs(w);
        }
    }
    return num[v]=sum;
}
int main(){
    while(scanf("%d",&V)==1 && V){
         scanf("%d",&E);
         Edge temp;
         int x,y,l;
         for(int i=1;i<=E;i++){
             scanf("%d%d%d",&x,&y,&l);
             temp.v=l, temp.to=y, edge[x].push_back(temp);
             temp.v=l, temp.to=x, edge[y].push_back(temp);
         }
         spfa(2);
         memset(num,0,sizeof(num));
         printf("%dn",dfs(1));
 
         for(int i=0;i<=V;i++)
             edge[i].clear();
         while(!que.empty())
              que.pop();
    }
    return 0;
}

3 Comments

  • Posted 20/11/2016 at 11:55 | Permalink

    Oh danke für die tolle Anntleuig! das muss ich doch auch mal probieren. Ist mir immer noch ein Rätsel, dass man da keine Naht sieht…LG Beate

  • Posted 30/12/2016 at 17:40 | Permalink

    sep14 YO CREO QUE YA BASTA CON ESTO NO SACAREMOS NADA CON HACERNOS LOS CHORITOS SI AL FINAL SALDREMOS PERDIENDO IGUAL, MEJOR SERA QUE TRABAJEMOS Y ACEPTEMOS ESTA OFERTA O QUIEREN MAS DESCUENTOS??????????

  • Posted 30/12/2016 at 19:38 | Permalink

    Temevo che la serie potesse implodere su se stessa.A differenza di Glauco le prime due serie le trovo ricchissime di spunti e suggestioni. Poi si son fatti prendere la mano per allungare il brodo, e il risultato ne è rimasto inficiato.

Post a Comment

Your email is kept private. Required fields are marked *