程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU-1596-find the safest road

HDU-1596-find the safest road

編輯:C++入門知識

SPFA算法


[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
int n,m,st,ed,front,rear; 
double mat[1005][1005],dis[1005]; 
int v[1005],q[1000001];  
void spfa() 

    int i,p; 
    while(front<rear) 
    { 
        p=q[front++]; 
        v[p]=0; 
        for(i=0;i<n;i++) 
        { 
            if(mat[p][i]==0||p==i) 
            continue; 
            if(dis[p]*mat[p][i]>dis[i]) 
            { 
                dis[i]=dis[p]*mat[p][i]; 
                if(!v[i]) 
                { 
                    q[rear++]=i; 
                    v[i]=1; 
                } 
            } 
        } 
    } 

int main() 

    int i,j; 
    while(scanf("%d",&n)!=EOF) 
    { 
        for(i=0;i<n;i++) 
        for(j=0;j<n;j++) 
        scanf("%lf",&mat[i][j]); 
        scanf("%d",&m); 
        while(m--) 
        { 
            scanf("%d%d",&st,&ed); 
            memset(v,0,sizeof(v)); 
            memset(dis,0,sizeof(dis)); 
            v[st-1]=1; 
            dis[st-1]=1; 
            front=0; 
            rear=1; 
            q[front]=st-1; 
            spfa(); 
            if(dis[ed-1]!=0) 
            printf("%.3lf\n",dis[ed-1]); 
            else 
            printf("What a pity!\n"); 
        } 
    } 
    return 0; 

 


作者;Cambridgeacm

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved