106 miles to Chicago - c++编程基础

根据乘法原理知道，概率是相乘的，但是直接相乘的话，题中的数据会超int。所以，我们把他转换成double先缩小倍数最后结果在乘回去，这个结果显然是正确的。别的就是最长路的求法了，没什么可讲的了。

下面给出三种不同的写法。

/*
    vector实现图的存储
*/

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int N = 100+5; struct Node { int to; double d; }; vector
        
          vet[N]; double SPFA(int s,int n) { queue
         
           q; bool inq[N]; double dis[N]; for(int i = 0;i <= n;++i){ inq[i] = 0; dis[i] = -1; } q.push(s); dis[s] = 1; inq[s] = 1; // printf("dis[n] = %lf\n",dis[n]); while(!q.empty()) { int v = q.front(); q.pop(); inq[v] = 0; for(int i = 0;i < int(vet[v].size());++i){ int u = vet[v][i].to; if(vet[v][i].d*dis[v] > dis[u]){ dis[u] = vet[v][i].d*dis[v]; // printf("dis[%d] = %lf \n",v,dis[v]); if(!inq[u]){ inq[u] = 1; q.push(u); } } } } return dis[n]; } int main() { int n,m,a,b; while(scanf("%d",&n),n) { for(int i = 0;i <= n;++i) vet[i].clear(); scanf("%d",&m); for(int i = 0;i < m;i++){ double p; Node node; scanf("%d%d%lf",&a,&b,&p); node.to = b; node.d = p*0.01; //缩小倍数 vet[a].push_back(node); node.to = a; node.d = p*0.01; vet[b].push_back(node); } double ans = SPFA(1,n); printf("%.6lf percent\n",ans*100.0); } }

/*
   邻接表实现
*/

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; const int N = 100+5; const double EPS = 1e-8; struct EDGE { int v,Next; double d; }edge[2*N*N]; int Head[2*N],E; void Add(int u,int v,double p) { edge[E].v = v; edge[E].d = p; edge[E].Next = Head[u]; Head[u] = E++; } double SPFA(int s,int n) { bool inq[N]; double dis[N]; queue
         
           q; memset(inq,0,sizeof(inq)); memset(dis,0,sizeof(dis)); q.push(s); dis[s] = 1; inq[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int i = Head[u];i != -1;i = edge[i].Next){ int v = edge[i].v; if(dis[u]*edge[i].d > dis[v]){ dis[v] = dis[u]*edge[i].d; if(!inq[v]){ inq[v] = 1; q.push(v); } } } } return dis[n]; } int main() { int m,n; while(scanf("%d",&n),n) { memset(Head,-1,sizeof(Head)); scanf("%d",&m); E = 0; for(int i = 0;i < m;++i) { int a,b; double p; scanf("%d%d%lf",&a,&b,&p); Add(a,b,p*0.01); Add(b,a,p*0.01); } double ans = SPFA(1,n); printf("%.6lf percent\n",ans*100.0); } return 0; }

/*
   Floy实现
*/

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int N = 100 + 5; double graph[N][N]; int n,m; void Init() { for(int i = 0;i < N;++i) for(int j = 0;j < N;++j) graph[i][j] = 0; } void Floy() { for(int k = 1;k <= n;k++){ for(int i = 1;i <= n;i++){ if(i == k)continue; for(int j = 1;j <= n;j++){ if(j==k||j==i)continue; // if(graph[i][k]==0.0||graph[k][j]==0.0)continue; if(graph[i][j] < graph[i][k]*graph[k][j]) graph[i][j] = graph[i][k]*graph[k][j]; } } } } int main() { while(scanf("%d",&n),n) { Init(); scanf("%d",&m); for(int i = 0;i < m;++i){ int a,b; double p; scanf("%d%d%lf",&a,&b,&p); graph[a][b] = graph[b][a] = p*0.01; } Floy(); printf("%.6lf percent\n",graph[1][n]*100.0); } return 0; }

106 miles to Chicago(二)