本身很简单的spfa判环 TLE了一把是因为没写map(不会)

看着别人的答案临时学了一发发现只是用的话还是挺简单的 (但是绝对别学别人直接命名为m) 800多MS水过

噢对了这题Pending到超时了三次 POI绝对有毒

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std; map<string, int> mapp;
double val[][];
int n, m; bool spfa(int s)
{
double dis[];
bool vis[];
int time[];
memset(dis, , sizeof dis);
memset(vis, , sizeof vis);
memset(time, , sizeof time); queue<int> q;
dis[s] = 1.0;
vis[s] = true;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i = ; i <= n; i++){
if(dis[i] < dis[u] * val[u][i]){
dis[i] = dis[u] * val[u][i];
if(!vis[i]){
vis[i] = true;
q.push(i);
if(++time[i] >= n) return true;
}
}
}
}
return false;
}
int main()
{
int kase = ;
while(){
cin >> n;
if(n == ) break;
memset(val, , sizeof val);
for(int i = ; i <= n; i++){
string str;
cin >> str;
mapp[str] = i;
}
cin >> m;
for(int i = ; i <= m; i++){
string str1, str2;
double value;
cin >> str1 >> value >> str2;
val[mapp[str1]][mapp[str2]] = value;
}
if(spfa()) cout << "Case " << ++kase << ": Yes" << endl;
else cout << "Case " << ++kase << ": No" << endl;
}
return ;
}

最新文章

  1. Node.js:dgram模块实现UDP通信
  2. Visual Studio 实用扩展推荐
  3. 使用bat/vbs/ahk对Windows下进行自动化操作
  4. Redis单机版本的安装
  5. python 生成器生成杨辉三角
  6. sql视图实例
  7. 关于C#不同位数相与或,或赋值时,隐藏位数扩展该留意的问题
  8. 问题:未能加载文件或程序集“System.Data.SQLite”或它的某一个依赖项。试图加载格式不正确的程序。
  9. Eclipse下使用Hadoop单机模式调试MapReduce程序
  10. Scala:(1)变量
  11. C# string.Format谨慎使用
  12. Build制作模型
  13. 找礼物(find)
  14. ajax传数组到后台,后台springmvc接收数组参数
  15. scrapy-redis功能简介
  16. 2010_3_1最新 完整 FFMPEG 编译详解
  17. python 工具安装
  18. JS ES6的变量的结构赋值
  19. python---RabbitMQ(1)简单队列使用,消息依次分发(一对一),消息持久化处理
  20. Git 提交更新到仓库(分布式版本控制系统)

热门文章

  1. ssh原理
  2. JavaScript:变量对象(Variable Object)
  3. lib静态链接库,dll动态链接库,h文件
  4. mine layer(2008 World Final C)
  5. QT5.4关联VS2010,配置VAssistX关联Qt类
  6. java语法学习问题总结
  7. html网页标题
  8. Java Abstract Class
  9. Eclipse的maven构建一个web项目,以构建SpringMVC项目为例
  10. NSArray,NSSet,NSDictionary的遍历,基本使用集锦