1009: 安全路径

dijkstra 轮询M次， floyd会超时

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1005;
double w[N][N];
double dist[N][N];
int vis[N];
struct cmp {bool operator()(const pair<int, double>& a, const pair<int, double>& b) {return a.second < b.second; // 大顶堆，second大的在前}
};
double dij(int s,int t){//cout<<1;memset(vis,0,sizeof(vis));priority_queue<pair<int, double>, vector<pair<int, double>>, cmp> que;//第一个是目的点，第二个是起点到目的点的成本 for(int i=1;i<=n;i++){que.push({i,dist[s][i]});}vis[s]=1;bool flag=0; //代表有没有找到s到t的最短路径 while(!flag){auto now = que.top();que.pop();if(now.first==t){flag=1;break;}if(vis[now.first]==1){continue;}else{for(int i=1;i<=n;i++){if(dist[s][i]<dist[s][now.first]*dist[now.first][i]){dist[s][i]=dist[s][now.first]*dist[now.first][i];que.push({i,dist[s][i]});}}}}return dist[s][t];
}
int main(){while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%lf",&dist[i][j]);}}int m;scanf("%d",&m);while(m--){int s,t;scanf("%d%d",&s,&t);if(dij(s,t)==0)printf("What a pity!\n");else printf("%.3lf\n",dist[s][t]);}}return 0;
}
//int main(){              //floyd写法错了50% 
//	while(scanf("%d",&n)!=EOF){
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=n;j++)
//				{
//					scanf("%lf",&w[i][j]);
//					dp[i][j]=w[i][j];
//				}
//		}
//		for(int k=1;k<=n;k++){
//			for(int i=1;i<=n;i++)
//				for(int j=1;j<=n;j++)
//					dp[i][j]=max(dp[i][j],dp[i][k]*dp[k][j]);
//		}
//		int m;
//		scanf("%d",&m);
//		while(m--){
//			int s,t;
//			scanf("%d%d",&s,&t);
//			if(dp[s][t]==0){
//				printf("What a pity!\n");
//			}
//			else
//				printf("%.3lf\n",dp[s][t]);
//		}
//	}
//}