[codevs1961]躲避大龙

题目←

对状态的设计意识还是太辣鸡了……
考虑各种拆点建图然而还是一脸不可做
然后滚去了兔子博客……
看见used[i][j]的定义就恍然了……

#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 10000 + 50;
struct edge
{int f,t,v;
}l[MAXN << 1];
int head[MAXN],next[MAXN << 1],tot,n,m;
void init(int n)
{for(int i = 1;i <= n;i ++)head[i] = -1;
}
bool used[MAXN][61];
int a,b,c;
void build(int f,int t,int v)
{l[++ tot] = (edge){f,t,v};next[tot] = head[f];head[f] = tot;
}
struct zt
{int num,dis;
};
queue  q;
string s;
void bfs(int x)
{used[x][0] = true;q.push((zt){x,0});while(!q.empty()){zt u = q.front();q.pop();for(int i = head[u.num];i != -1;i = next[i]){int t = l[i].t;int v = (u.dis + l[i].v)%60;while(v < 0)v += 60;if(!used[t][v])q.push((zt){t,v});used[t][v] = true;}}
}
int cnt;
int main()
{while(cin >> s){scanf("%d%d",&n,&m);init(n);memset(used,0,sizeof(used));tot = 0;for(int i = 1;i <= m;i ++){scanf("%d%d%d",&a,&b,&c);build(a,b,c);build(b,a,c);}bfs(1);used[2][60] = true;for(int i = 0;i <= 60;i ++){if(used[2][i]){printf("Output%d:\n%02d\n",++ cnt,i);break;}}}return 0;
}

Tips:
BFS有个每个搜索点只会入队一次的很好的性质（判重来实现）
总的搜索状态数最多为n*60，而n <= 7000，是完全可以承受的
其实想到BFS了，没考虑到复杂度于是没敢写

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！