hdu1217

Hdu 1217この問題は伝統的な最短ルートを突破したが、思想は同じで、斬新な問題だ.
2つの方法で1つはSpfa 2つはFloyd(--やっとFloydが使えるようになって、ずっとチャンスがなかった)
Spfa                        Floyd                
                   
しかしSpfaアルゴリズムを用いた場合,処理ループの問題ネット上の問題解はキューループにif(dis[開始]>1.0)returntureを加えたものであり,私はキューループを処理した後にこの判断を加えたが,発見時間が10数倍も調べられ,不思議な感じがした.(PS:前者にはもう一つのメリットがあり、ループの問題を処理しない)
Spfa

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<list>
using namespace std; typedef long long lld; typedef unsigned int ud;
#define Inf INT_MAX/2//int  
#define Min(x,y) (x)<(y)?(x):(y)
#define Max(x,y) (x)>(y)?(x):(y)
#define PQ priority_queue
#define Q queue
#define N 33
int n,m; struct Node { int v,next; double w; }edge[N*N]; double dis[N]; int mark[N],head[N],cnt[N]; char str[N*N][N]; char buff[N]; int GetCur(char *s) { for(int i=1;i<=n;i++) if(strcmp(s,str[i])==0) return i; return -1; } bool Spfa(int s) {
    memset(dis,0,sizeof dis);
    memset(mark,0,sizeof mark);
    memset(cnt,0,sizeof cnt);

    dis[s]=1.0; mark[s]=1;
    Q<int> q;
    q.push(s); while(!q.empty()) { int e=q.front(); q.pop();
        mark[e]=0; for(int i=head[e];i!=-1;i=edge[i].next) { int v=edge[i].v; if(dis[e]*edge[i].w>dis[v]) {
                dis[v]=dis[e]*edge[i].w; if(!mark[v]) {
                    q.push(v);
                    mark[v]=1; if(++cnt[v]>n) break; } } } } if(dis[s]>1.0) return true; return false; } int main() { int cas=1; while(scanf("%d",&n)&&n) {
        memset(head,-1,sizeof head); for(int i=1;i<=n;i++)
            scanf("%s",str[i]);
        scanf("%d",&m); for(int i=1;i<=m;i++) { int u,v; double w;
            scanf("%s",buff);
            u=GetCur(buff);
            scanf("%lf%s",&w,buff);
            v=GetCur(buff);
            
            edge[i].v=v;
            edge[i].w=w;
            edge[i].next=head[u];
            head[u]=i; } int find=false; for(int i=1;i<=n;i++) { if(Spfa(i)) {
                find=true; break; } }
        printf("Case %d: ",cas++); if(find)
            printf("Yes
"); else
            printf("No
"); } return 0; }

Floyd

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<list>
using namespace std; typedef long long lld; typedef unsigned int ud;
#define Inf INT_MAX/2//int  
#define Min(x,y) (x)<(y)?(x):(y)
#define Max(x,y) (x)>(y)?(x):(y)
#define PQ priority_queue
#define Q queue
#define N 33
double map[N][N]; char str[N*N][N]; char a[N],b[N]; int n,m; int u,v; double w; int GetCur(char *s) { for(int i=1;i<=n;i++) if(strcmp(s,str[i])==0) return i; return -1; } void Floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(map[i][k]*map[k][j]>map[i][j])
                    map[i][j]=map[i][k]*map[k][j]; } int main() { int cas=1; while(scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j)
                    map[i][j]=1.0; else
                    map[i][j]=0.0; } for(int i=1;i<=n;i++)
            scanf("%s",str[i]);
        scanf("%d",&m); for(int i=1;i<=m;i++) {
            scanf("%s%lf%s",a,&w,b);
            u=GetCur(a);
            v=GetCur(b);
            map[u][v]=w; }
        Floyd(); int find=false; for(int i=1;i<=n;i++) if(map[i][i]>1.0)
                find=true;
        printf("Case %d: ",cas++); if(find)
            printf("Yes
"); else
            printf("No
"); } return 0; }
/*
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0

*/