ZZULIOJ 1925: 信道安全（Dijkstra，Spfa）

1925: 信道安全

先来一个 超时 and 超内存 的 Floyd 算法，深刻理解一下本题的含义

#include<stdio.h>
double e[10010][10010];
int main()
{
    int t;scanf("%d",&t);while(t--){
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
    if(i==j) e[i][j]=1;else e[i][j]=0;}while(m--){
    int a,b;double c;scanf("%d%d%lf",&a,&b,&c);e[a][b]=e[b][a]=c/100;}for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
    if(e[i][j]<e[i][k]*e[k][j])e[i][j]=e[i][k]*e[k][j];}printf("%.6f\n",100*e[1][n]);}return 0; 
}

堆优化版的Dijkstra算法

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<double,int> PDI; 
const int N = 10010, M = 50010;
int n,m,idx;
int h[N],e[M],w[M],ne[M];
double dist[N];
bool st[N];
void add(int a,int b,int c)  // 添加一条边a->b，边权为c
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(int s)  //求 s 号点到 n 号点的最短路距离
{
    memset(dist,0,sizeof dist);dist[s]=1; 		//自身到自身的概率为1 priority_queue<PDI> heap;	// 默认是大根堆 heap.push((PDI){
    1.0,s});		// first存储距离，second存储节点编号while(!heap.empty()){
    PDI t=heap.top();heap.pop();int ver=t.second;if(st[ver]) continue;st[ver]=true;for(int i=h[ver];~i;i=ne[i]){
    int j=e[i];if(dist[j]<dist[ver]*w[i]/100){
    dist[j]=dist[ver]*w[i]/100;heap.push((PDI){
    dist[j],j});}}}
}
int main()
{
    int t;scanf("%d",&t);while(t--){
    memset(h,-1,sizeof h);memset(st,false,sizeof st);idx=0;scanf("%d%d",&n,&m);while(m--){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}dijkstra(1);printf("%.6f\n",dist[n]*100);}return 0;
}

Spfa，链式前向星

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;const int N = 10010, M = 50010;int n,m,idx;
int h[N],e[M],w[M],ne[M];
double dist[N];
bool st[N];void add(int a,int b,int c)  // 添加一条边a->b，边权为c
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}void spfa(int s)
{
    queue<int>Q;memset(dist,0,sizeof dist);dist[s]=1;st[s]=true;Q.push(s);while(!Q.empty()){
    int t=Q.front();Q.pop();st[t]=false;//从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队for(int i=h[t];i!=-1;i=ne[i]){
    int j=e[i];if(dist[j]<dist[t]*w[i]/100){
    dist[j]=dist[t]*w[i]/100;if(!st[j])//当前已经加入队列的结点，无需再次加入队列，即便发生了更新也只用更新数值即可，重复添加降低效率{
    Q.push(j);st[j]=true;}}}}
}
int main()
{
    int t;scanf("%d",&t);while(t--){
    memset(h,-1,sizeof h);memset(st,false,sizeof st);idx=0;scanf("%d%d",&n,&m);while(m--){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}spfa(1);				printf("%.6f\n",dist[n]*100);}return 0;
}