/ Vijos / 题库 / 小胖抗日 /

题解

36 条题解

  • 3
    @ 2017-05-02 08:30:20

    楼下smg
    裂点bfs。。。无非就是vis数组二维就可以了
    开k个邻接矩阵就可以了

    #include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<cstring>
#include<vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Dow(i,j,k) for(int i=k;i>=j;i--)
using namespace std;
int n,m,k,l,r,mp[101][101][11],q[1001],tim[1001];
bool vis[101][11];
int main()
{
    scanf("%d%d",&n,&m);
    For(i,1,m)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        mp[x][y][0]=mp[y][x][0]=1;
    }
    scanf("%d",&k);
    For(i,1,n)  mp[i][i][0]=1;
    For(i,1,k)
        For(j,1,n)  For(t,1,n)  mp[j][t][i]=mp[j][t][0];
    if(k!=0)
    For(i,0,k-1)
    {
        int x=1,y=1;
        while(1)
        {
            scanf("%d%d",&x,&y);
            if(x==0&&y==0)  break;
            mp[x][y][i]=mp[y][x][i]=0;
        }
    }
    q[1]=1;tim[1]=0;
    vis[1][0]=1;
    l=1;r=1;
    while(l<=r)
    {
        int t=q[l];
        if(t==n)
        {
            printf("%d",tim[l]);
            return 0;
        }
        For(i,1,n)
            if(k!=0)
            {
                if(mp[t][i][tim[l]%k]&&!vis[i][(tim[l]+1)%k])
                    q[++r]=i,tim[r]=tim[l]+1,vis[i][(tim[l]+1)%k]=1;
            }else
            {
                if(mp[t][i][0]&&!vis[i][0])
                    q[++r]=i,tim[r]=tim[l]+1,vis[i][0]=1;
            }
        l++;
    }
    printf("No solution.\n");
}
  • 1
    @ 2018-08-03 15:22:30

    BFS

    两个注意点
    1.要用vis判重，如果是普通的bfs求最短路，因为状态数少就不必要判重，但是这样可能会无解从而无限扩展
    2.k可能等于0，在%k的时候要特判

    #include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double PI=3.1415926;
const double eps=1e-8;

int n,m,k;
bool del[21][201][201];
vector<int> g[201];
bool vis[201][21];
struct node {
    int id;
    int t;
    int cnt;
};
queue<node> q;
void bfs() {
    q.push(node{1,0,0});
    vis[1][0]=1;
    bool ok=0;
    while (q.size()) {
        node x=q.front();q.pop();
        if (x.id==n) {
            cout<<x.t<<endl;
            ok=1;
            break;
        }
        int t=x.t;
        for (int i=0;i<g[x.id].size();i++) {
            int y=g[x.id][i];
            if (del[(k?(t%k+1):t+1)][x.id][y]==0) {
                if (vis[y][(k?(t%k+1):t+1)]==0) {
                    q.push(node{y,t+1,0});
                    vis[y][(k?(t%k+1):t+1)]=1;
                }
            }
        }
        if (vis[x.id][(k?(t%k+1):t+1)]==0) {
            q.push(node{x.id,t+1,x.cnt+1});
            vis[x.id][(k?(t%k+1):t+1)]=1;
        }
    }
    if (!ok) cout<<"No solution."<<endl;
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,m) {
        int x,y;
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    cin>>k;
    FOR(i,k) {
        int x,y;
        while (cin>>x>>y) {
            if (x==0&&y==0) break;
            del[i][x][y]=del[i][y][x]=1;
        }
    }
    bfs();
    return 0;
}
  • 0
    @ 2022-02-27 16:04:14

    首页
    题库
    训练
    讨论
    比赛
    作业
    排名
    real_hdsy_gyz
    / Vijos / 题库 / 小胖抗日 /
    题解
    35 条题解
    0
    real_hdsy_gyz LV 0
    发表您的题解
    3

    Fop_zz LV 10 @ 4 年前
    楼下smg
    裂点bfs。。。无非就是vis数组二维就可以了
    开k个邻接矩阵就可以了

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #include<string>
    #include<map>
    #include<cstring>
    #include<vector>
    #define inf 1e9
    #define ll long long
    #define For(i,j,k) for(int i=j;i<=k;i++)
    #define Dow(i,j,k) for(int i=k;i>=j;i--)
    using namespace std;
    int n,m,k,l,r,mp[101][101][11],q[1001],tim[1001];
    bool vis[101][11];
    int main()
    {
    scanf("%d%d",&n,&m);
    For(i,1,m)
    {
    int x,y;
    scanf("%d%d",&x,&y);
    mp[x][y][0]=mp[y][x][0]=1;
    }
    scanf("%d",&k);
    For(i,1,n) mp[i][i][0]=1;
    For(i,1,k)
    For(j,1,n) For(t,1,n) mp[j][t][i]=mp[j][t][0];
    if(k!=0)
    For(i,0,k-1)
    {
    int x=1,y=1;
    while(1)
    {
    scanf("%d%d",&x,&y);
    if(x==0&&y==0) break;
    mp[x][y][i]=mp[y][x][i]=0;
    }
    }
    q[1]=1;tim[1]=0;
    vis[1][0]=1;
    l=1;r=1;
    while(l<=r)
    {
    int t=q[l];
    if(t==n)
    {
    printf("%d",tim[l]);
    return 0;
    }
    For(i,1,n)
    if(k!=0)
    {
    if(mp[t][i][tim[l]%k]&&!vis[i][(tim[l]+1)%k])
    q[++r]=i,tim[r]=tim[l]+1,vis[i][(tim[l]+1)%k]=1;
    }else
    {
    if(mp[t][i][0]&&!vis[i][0])
    q[++r]=i,tim[r]=tim[l]+1,vis[i][0]=1;
    }
    l++;
    }
    printf("No solution.\n");
    }
    Copy
    1

    Goodhao LV 10 @ 3 年前
    BFS

    两个注意点
    1.要用vis判重，如果是普通的bfs求最短路，因为状态数少就不必要判重，但是这样可能会无解从而无限扩展
    2.k可能等于0，在%k的时候要特判

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7777777;
    const double PI=3.1415926;
    const double eps=1e-8;

    int n,m,k;
    bool del[21][201][201];
    vector<int> g[201];
    bool vis[201][21];
    struct node {
    int id;
    int t;
    int cnt;
    };
    queue<node> q;
    void bfs() {
    q.push(node{1,0,0});
    vis[1][0]=1;
    bool ok=0;
    while (q.size()) {
    node x=q.front();q.pop();
    if (x.id==n) {
    cout<<x.t<<endl;
    ok=1;
    break;
    }
    int t=x.t;
    for (int i=0;i<g[x.id].size();i++) {
    int y=g[x.id][i];
    if (del[(k?(t%k+1):t+1)][x.id][y]==0) {
    if (vis[y][(k?(t%k+1):t+1)]==0) {
    q.push(node{y,t+1,0});
    vis[y][(k?(t%k+1):t+1)]=1;
    }
    }
    }
    if (vis[x.id][(k?(t%k+1):t+1)]==0) {
    q.push(node{x.id,t+1,x.cnt+1});
    vis[x.id][(k?(t%k+1):t+1)]=1;
    }
    }
    if (!ok) cout<<"No solution."<<endl;
    }
    int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,m) {
    int x,y;
    cin>>x>>y;
    g[x].pb(y);
    g[y].pb(x);
    }
    cin>>k;
    FOR(i,k) {
    int x,y;
    while (cin>>x>>y) {
    if (x==0&&y==0) break;
    del[i][x][y]=del[i][y][x]=1;
    }
    }
    bfs();
    return 0;
    }
    Copy
    0

    PowderHan LV 10 @ 4 年前
    /*
    好题Orz..
    第一道搜索题自己想出思路后在半个小时内两次调出了~！
    一开始看到这道题
    觉得没法搜索啊
    如果裸的直接bfs会不会太慢啊
    (事实证明虽然没有这种做法快但是也不会T的)
    然后就想到要不用SPFA来做？
    那怎么表示状态？
    到达某个点？
    不行啊如果d[u]代表到达u点的状态
    那可能有更小的d[u]但是要等待更久
    不具有无后效性啊
    那定义d[u][t]表示第t时间到达u的最小时间？
    哎呀傻逼了窝直接记录周期不就好了吗？
    那么很容易有这么一个表示状态的方法
    d[u][t]表示在第t个周期到达了u点的最小时间
    那么我们很容易证明这个定义是正确可行的
    因为这样完整无误地表达了一个状态
    并且是具有无后效性和最优子结构的
    那么很容易写出这样一个SPFA了
    周期的话直接用一个数组nocan[k][u][v]
    表示在第k个周期能否从u到v
    那么扩展的时候我们对于所有的相邻点
    只需要用一个循环来找到最近的周期能到
    注意这里如果t加了k次了还不能到v
    说明这条路是一直封住的
    那么就必要要及时退出(第一次就是忘了break)
    然后数据会有k==0的情况
    必须要有if(k==0) k++
    不然除数为0就炸了(还好窝机智地猜测到惹23333)
    然后这题就水出来了
    具体自己看一看叭~
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;

    const int MAXN=120;
    const int MAXK=15;
    const int INF=(1<<30)-1;
    struct Edge
    {
    int to,next;
    }e[MAXN<<4];
    int fisrt[MAXN];
    struct Node
    {
    int poss,time;
    };
    int d[MAXN][MAXK];
    int in[MAXN][MAXK];
    bool nocan[MAXK][MAXN][MAXN];
    queue<Node> q;
    int n,m,k,tot;
    int ans=INF;

    inline void Add_Edge(int& x,int& y)
    {
    e[++tot].to=y; e[tot].next=fisrt[x]; fisrt[x]=tot;
    }

    void init()
    {
    memset(fisrt,-1,sizeof(fisrt));
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d",&x,&y);
    Add_Edge(x,y); Add_Edge(y,x);
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++)
    {
    while(scanf("%d%d",&x,&y)==2)
    {
    if(x==0||y==0)
    break;
    nocan[i][x][y]=nocan[i][y][x]=1;
    }
    }
    if(k==0)

    k++;
    for(int i=1;i<=n;i++)
    for(int j=0;j<k;j++)
    d[i][j]=INF;
    }

    void SPFA()
    {
    d[1][0]=0; in[1][0]=1; q.push((Node){1,0});
    Node x;
    while(!q.empty())
    {
    x=q.front(); q.pop();
    int& u=x.poss; int& time=x.time; bool flag;
    in[u][time%k]=0;
    for(int i=fisrt[u];i!=-1;i=e[i].next)
    {
    int& v=e[i].to;
    int t=time; flag=0;
    while(nocan[t%k][u][v])
    {
    t++;
    if(t-time>k+1)
    {
    flag=1;
    break;
    }
    }
    if(flag)
    continue;
    if(t+1<d[v][t%k])
    {
    d[v][t%k]=t+1;
    if(!in[v][t%k])
    {
    in[v][t%k]=1;
    q.push((Node){v,t+1});
    }
    }
    }

    }
    for(int i=0;i<k;i++)
    ans=min(ans,d[n][i]);
    if(ans==INF)
    cout<<"No solution."<<endl;
    else
    cout<<ans<<endl;
    }

    int main()
    {
    init();
    SPFA();
    return 0;
    }

    Copy
    0

    wang_yanheng LV 10 @ 5 年前
    扩展SPFA即可秒杀。SPFA时，到达每个点的最短时间被记录在数组 A 里（A 等价于最短路中的最小距离数组）。假设目前从队列取出的节点为 u，枚举与其相连的点 v，找出 u -> v 最快能在多久之后接通，然后依照规则更新。

    说一下注意事项：
    - 图是双向的
    - 第二个测试点 k=0，mod的时候要小心

    放一段代码

    for(v=1; v<=numV; v++){
    if(G[u][v]){ //若 u, v 之间联通
    if(cycle > 0){
    for(i=0; i<cycle; i++){ //找出多久之后没人巡逻
    if(!banned[(minTime[u]+i)%cycle][u][v])
    break;
    }
    if(!banned[(minTime[u]+i)%cycle][u][v] && minTime[v]>minTime[u]+i+1){ //更新
    minTime[v] = minTime[u]+i+1;
    if(!using[v]){
    using[v] = 1;
    queue[tail++] = v;
    }
    }
    }else{
    if(minTime[v] > minTime[u]+1){
    minTime[v] = minTime[u]+1;
    if(!using[v]){
    using[v] = 1;
    queue[tail++] = v;
    }
    }
    }
    }
    }

    0

    Marcha LV 7 @ 5 年前
    BFS改造（重复入队）+散列
    c++
    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #define maxn 120
    #define maxk 15
    using namespace std;
    struct node{int t,inqn,nd;};
    struct check{int f,t;};
    vector<int> map[maxn];
    vector<check> ck[maxk];
    queue<node> que;
    int N,M,K,vis[maxn]={0};
    int jud(int time,int f,int t){
    time%=K;
    for(int i=0;i<ck[time].size();i++){
    if(ck[time][i].f==f && ck[time][i].t==t) return 0;
    }
    return 1;
    }
    int bfs(int T){
    int save;
    node tmp,enew;
    tmp.t=0,tmp.inqn=1,tmp.nd=T;
    que.push(tmp); vis[T]=1;
    while(!que.empty()){
    save=0;
    tmp=que.front(); que.pop(); //printf("%d %d %d\n",tmp.t,tmp.inqn,tmp.nd);
    if(tmp.nd==N)
    return tmp.t;//reach
    for(int i=0;i<map[tmp.nd].size();i++){
    if(jud(tmp.t,tmp.nd,map[tmp.nd][i]) && vis[map[tmp.nd][i]]==0){
    enew.t=tmp.t+1,enew.nd=map[tmp.nd][i],enew.inqn=1;
    que.push(enew);//go
    vis[map[tmp.nd][i]]=1;
    }else save=1;
    }
    if(save == 1 && tmp.inqn <= K){tmp.inqn++,tmp.t++; que.push(tmp);}//hide
    }
    return -1;
    }
    int main(){
    int f,t;
    node tmp; check tmpck;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
    scanf("%d%d",&f,&t);
    map[f].push_back(t);
    map[t].push_back(f);
    }
    scanf("%d",&K);
    for(int i=0;i<K;i++)
    while(scanf("%d%d",&f,&t) && (f!=0 && t!=0)){
    tmpck.f=f,tmpck.t=t;
    ck[i].push_back(tmpck);
    tmpck.f=t,tmpck.t=f;
    ck[i].push_back(tmpck);
    }//read
    f=bfs(1);
    if(f==-1)
    printf("No solution.\n");
    else printf("%d\n",f);
    return 0;
    }

    0

    756242668 LV 6 @ 7 年前
    program p1089;
    var
    f:array[1..100,1..10] of longint;
    n,m:longint;
    sf:array[1..100,1..100,1..10] of boolean;
    loc:array[1..100,1..500] of byte;
    d:array[1..100] of integer;
    i,t,x,y,ans,k:longint;
    que1,que2:array[1..1001] of longint;
    vis:array[1..100,1..10] of boolean;
    procedure bfs;
    var
    i:longint;
    link,tail:longint;
    begin
    link:=1;
    tail:=1;
    que1[1]:=1;
    que2[1]:=1;
    while (que1[link]<n)and(link<=1000) do begin
    for i:=1 to d[que1[link]] do begin if sf[que1[link],loc[que1[link],i],que2[link]] then if not(vis[loc[que1[link],i],que2[link]]) then begin inc(tail); que1[tail]:=loc[que1[link],i]; que2[tail]:=que2[link]+1; if que2[tail]>k then que2[tail]:=1; f[que1[tail],que2[tail]]:=f[que1[link],que2[link]]+1; vis[que1[tail],que2[tail]]:=true; end; end; inc(que2[link]);
    if que2[link]>k then que2[link]:=1;
    if not(vis[que1[link],que2[link]]) then begin
    vis[que1[link],que2[link]]:=true; tail:=tail+1; que1[tail]:=que1[link]; que2[tail]:=que2[link]; dec(que2[link]); if que2[link]=0 then que2[link]:=k; f[que1[tail],que2[tail]]:=f[que1[link],que2[link]]+1; end; link:=link+1;
    end;
    ans:=f[que1[link],que2[link]];
    end;
    begin
    fillchar(vis,sizeof(vis),false);
    fillchar(sf,sizeof(sf),true);
    fillchar(d,sizeof(d),0);
    readln(n,m);
    for i:=1 to m do begin
    readln(x,y); d[x]:=d[x]+1; loc[x,d[x]]:=y; d[y]:=d[y]+1; loc[y,d[y]]:=x; end; readln(k);
    t:=1;
    while t<=k do begin
    readln(x,y); if (x=0)and(y=0) then t:=t+1 else begin sf[x,y,t]:=false; sf[y,x,t]:=false; end; end; bfs;
    if ans<=0 then writeln('No solution.')
    else writeln(ans); end.

    0

    SUNYU123 LV 8 @ 7 年前
    program vijos1089;
    var s,i,j,min,x1,y1,i1,k,m,n:longint;
    v:array[0..500,0..500]of boolean;
    a:array[0..10,0..600,0..600]of longint;
    f:array[0..50000]of longint;
    g:array[0..2000,0..2000]of longint;
    x,y:array[0..50000]of longint;
    procedure dfs(s,t,len,dd:longint);
    var i,j,o,l:longint;
    begin
    if (len>min)or(dd=k+1) then exit;
    if t=n then
    begin
    if len<min then
    begin
    min:=len;
    end;
    exit;
    end;
    if (k>0) then
    dfs(s+1,t,len+1,dd+1);
    if s>k then s:=s-k;
    for i:=1 to g[t,0] do
    if ((a[s,t,g[t,i]]=1)or(k=0))and(f[g[t,i]]>f[t]+1)and(v[t,g[t,i]]) then
    begin
    v[t,g[t,i]]:=false;
    v[g[t,i],t]:=false;
    o:=f[g[t,i]];
    f[g[t,i]]:=f[t]+1;
    dfs(s+1,g[t,i],len+1,0);
    f[g[t,i]]:=o;
    v[t,g[t,i]]:=true;
    v[g[t,i],t]:=true;
    end;
    end;
    begin
    fillchar(v,sizeof(v),true);
    readln(n,m);
    fillchar(f,sizeof(f),$7f);
    f[1]:=0;
    for i:=1 to m do
    begin
    readln(x[i],y[i]);
    inc(g[x[i],0]);g[x[i],g[x[i],0]]:=y[i];
    inc(g[y[i],0]);g[y[i],g[y[i],0]]:=x[i];
    end;
    readln(k);
    for i:=1 to k do
    for j:=1 to n do
    for i1:=1 to n do
    a[i,j,i1]:=1;
    s:=1;
    while s<=k do
    begin
    readln(x1,y1);
    if (x1=0)and(y1=0) then
    inc(s)
    else
    a[s,x1,y1]:=0;
    end;
    min:=maxlongint;
    dfs(1,1,0,0);
    if min<maxlongint then
    writeln(min)
    else
    writeln('No solution.');
    end.
    6 7 过不去;求改错.

    0

    whbjzzwjxq LV 8 @ 7 年前
    program p1089;
    var
    f:array[1..100,1..10] of longint;
    n,m:longint;
    sf:array[1..100,1..100,1..10] of boolean;
    loc:array[1..100,1..500] of byte;
    d:array[1..100] of integer;
    i,t,x,y,ans,k:longint;
    que1,que2:array[1..1001] of longint;
    vis:array[1..100,1..10] of boolean;
    procedure bfs;
    var
    i:longint;
    link,tail:longint;
    begin
    link:=1;
    tail:=1;
    que1[1]:=1;
    que2[1]:=1;
    while (que1[link]<n)and(link<=1000) do begin
    for i:=1 to d[que1[link]] do begin
    if sf[que1[link],loc[que1[link],i],que2[link]] then
    if not(vis[loc[que1[link],i],que2[link]]) then begin
    inc(tail);
    que1[tail]:=loc[que1[link],i];
    que2[tail]:=que2[link]+1;
    if que2[tail]>k then que2[tail]:=1;
    f[que1[tail],que2[tail]]:=f[que1[link],que2[link]]+1;
    vis[que1[tail],que2[tail]]:=true;
    end;
    end;
    inc(que2[link]);
    if que2[link]>k then que2[link]:=1;
    if not(vis[que1[link],que2[link]]) then begin
    vis[que1[link],que2[link]]:=true;
    tail:=tail+1;
    que1[tail]:=que1[link];
    que2[tail]:=que2[link];
    dec(que2[link]);
    if que2[link]=0 then que2[link]:=k;
    f[que1[tail],que2[tail]]:=f[que1[link],que2[link]]+1;
    end;
    link:=link+1;
    end;
    ans:=f[que1[link],que2[link]];
    end;
    begin
    fillchar(vis,sizeof(vis),false);
    fillchar(sf,sizeof(sf),true);
    fillchar(d,sizeof(d),0);
    readln(n,m);
    for i:=1 to m do begin
    readln(x,y);
    d[x]:=d[x]+1;
    loc[x,d[x]]:=y;
    d[y]:=d[y]+1;
    loc[y,d[y]]:=x;
    end;
    readln(k);
    t:=1;
    while t<=k do begin
    readln(x,y);
    if (x=0)and(y=0) then t:=t+1
    else begin sf[x,y,t]:=false; sf[y,x,t]:=false; end;
    end;
    bfs;
    if ans<=0 then writeln('No solution.')
    else writeln(ans);
    end.
    这题难度有3？？？建议设成2简单的判重+边储存

    0

    SEX丶Elope LV 6 @ 9 年前
    点击查看程序源码+详细题解

    0

    hsez_zyf LV 10 @ 9 年前
    这个题呢可以用SPFA解决。每次需要扩展一个点的时候，对其的扩展结点进行判断，看看是否有人巡逻，如果有，那么等待，时间+1需要注意的是这个题全部都是双向边。还有注意一下，每次有人巡逻的时候时间+1需要继续判断，所以我是通过一个深搜来完成的。然后如果在一个点等着总是有人巡逻的话怎么办呢？那么我们进行判断，只要等待的时间>k的时候直接返回不能。就解决了。。。注意一下都是双向边。

    欢迎来我的间： http://hi.baidu.com/samroxas/item/7461ac59d3e838d9d48bacf7

    附代码：

    program vijos1089;

    var

    wait,time,x,now,n,m,k,a,b,total,i,sum,head,tail,next,nextt,y,temp:longint;

    map:array[1..100] of longint;

    save:array[1..1000,1..2] of longint;

    check:array[1..100,1..100] of longint;

    line:array[1..5000,1..2] of longint;

    dist,queue:array[1..100] of longint;

    flag:array[1..100] of boolean;

    procedure add(i,j:longint);

    begin

    inc(total);

    save[total,1]:=j;

    save[total,2]:=map[i];

    map[i]:=total;

    end;

    function deal(a,b,now:longint):longint;

    var

    y,temp,store:longint;

    begin

    if time>k then

    exit(-1);

    deal:=0;

    y:=check[a,b];

    while y-1 do

    begin

    temp:=now mod k;

    if temp=0 then

    temp:=k;

    if temp=line[y,1] then

    begin

    inc(time);

    store:=deal(a,b,now+1);

    if store=-1 then

    exit(-1);

    end;

    y:=line[y,2];

    end;

    end;

    begin

    readln(n,m);

    fillchar(map,sizeof(map),(ff);
    fillchar(check,sizeof(check),)ff);

    for i:=1 to m do

    begin

    readln(a,b);

    add(a,b);

    add(b,a);

    end;

    readln(k);

    for i:=1 to k do

    begin

    readln(a,b);

    while (a0) and (b0) do

    begin

    inc(sum);

    line[sum,1]:=i;

    line[sum,2]:=check[a,b];

    check[a,b]:=sum;

    inc(sum);

    line[sum,1]:=i;

    line[sum,2]:=check;

    check:=sum;

    readln(a,b);

    end;

    end;

    head:=0;

    tail:=1;

    queue[1]:=1;

    fillchar(dist,sizeof(dist),$7f);

    dist[1]:=0;

    flag[1]:=true;

    while headtail do

    begin

    head:=(head mod 100)+1;

    now:=queue[head];

    flag[now]:=false;

    x:=map[now];

    while x-1 do

    begin

    next:=save[x,1];

    nextt:=dist[now]+1;

    if k0 then

    begin

    time:=0;

    wait:=deal(now,next,nextt);

    if wait=-1 then

    break;

    nextt:=nextt+time;

    end;

    if nextt

    0

    新建文件夹 LV 10 @ 9 年前
    题目都没说是无向边好像。。。然后注意k的范围

    0

    93狒狒 LV 9 @ 12 年前
    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    认真分析题......

    注意在有的周期里哪条边都不能走......

    0

    zhujf553 LV 10 @ 12 年前
    用类似SPFA的BFS过了，要注意一条边可能在不同周期内巡逻多次

    0

    陈亮宇 LV 10 @ 12 年前
    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    o(╯□╰)o No solution 后面有一个点号。。。

    0

    181818181818 LV 10 @ 12 年前
    直接暴搜即可

    夏润神用bellman-ford，太牛逼了

    0

    怪盗~基德 LV 10 @ 12 年前
    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    0

    luyifan LV 10 @ 13 年前
    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    用dfs+hash即可,hash[i,t mod k]用来记录到第i点第t mod k的最优值,注意remember躲藏.

    0

    LittleRock LV 8 @ 13 年前
    问一下：第二点的数据是什么？

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：运行超时...

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    No solution.的情况没有处理好 = =

    0

    oimaster LV 10 @ 13 年前
    BFS+Hash=AC

    注意一下k=0的特殊情况。还有边是无向的。

    0

    voyagec2 LV 10 @ 13 年前
    简单BFS

    HASH表判重

    I表示接点,J表示周期

    HASH表示在周期的第J分钟到I接点的最小时间

    这里如果用到MOD K 要小心,第3个点K=0 即无巡逻的鬼子

    特殊处理一下即可:IF K=0 THEN K:=1;

    1 2 下一页 › 末页 »
    小胖抗日
    查看题目
    递交
    讨论
    题解
    信息
    ID1089递交 Accepted难度7分类点击显示标签
    小胖系列
    递交数797我的递交数1已通过160通过率20%被复制5上传者 huyichen
    状态
    评测队列
    服务状态
    开发
    开源
    API
    支持
    帮助
    QQ 群
    关于联系我们隐私服务条款版权申诉 Language
    © 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

  • 0
    @ 2017-05-07 22:41:12 
    /*
好题Orz..
第一道搜索题自己想出思路后在半个小时内两次调出了~！
一开始看到这道题
觉得没法搜索啊
如果裸的直接bfs会不会太慢啊
(事实证明虽然没有这种做法快但是也不会T的)
然后就想到要不用SPFA来做？
那怎么表示状态？
到达某个点？
不行啊如果d[u]代表到达u点的状态
那可能有更小的d[u]但是要等待更久
不具有无后效性啊
那定义d[u][t]表示第t时间到达u的最小时间？
哎呀傻逼了窝直接记录周期不就好了吗？
那么很容易有这么一个表示状态的方法
d[u][t]表示在第t个周期到达了u点的最小时间
那么我们很容易证明这个定义是正确可行的
因为这样完整无误地表达了一个状态
并且是具有无后效性和最优子结构的
那么很容易写出这样一个SPFA了
周期的话直接用一个数组nocan[k][u][v]
表示在第k个周期能否从u到v
那么扩展的时候我们对于所有的相邻点
只需要用一个循环来找到最近的周期能到
注意这里如果t加了k次了还不能到v
说明这条路是一直封住的
那么就必要要及时退出(第一次就是忘了break)
然后数据会有k==0的情况
必须要有if(k==0)    k++
不然除数为0就炸了(还好窝机智地猜测到惹23333)
然后这题就水出来了
具体自己看一看叭~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN=120;
const int MAXK=15;
const int INF=(1<<30)-1;
struct Edge
{
    int to,next;
}e[MAXN<<4];
int fisrt[MAXN];
struct Node
{
    int poss,time;
};
int d[MAXN][MAXK];
int in[MAXN][MAXK];
bool nocan[MAXK][MAXN][MAXN];
queue<Node> q;
int n,m,k,tot;
int ans=INF;

inline void Add_Edge(int& x,int& y)
{
    e[++tot].to=y;  e[tot].next=fisrt[x];   fisrt[x]=tot;
}

void init()
{
    memset(fisrt,-1,sizeof(fisrt));
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        Add_Edge(x,y);  Add_Edge(y,x);
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++)
    {
        while(scanf("%d%d",&x,&y)==2)
        {
            if(x==0||y==0)
                break;
            nocan[i][x][y]=nocan[i][y][x]=1;
        }
    }
    if(k==0)    
        k++;
    for(int i=1;i<=n;i++)
        for(int j=0;j<k;j++)
            d[i][j]=INF;
}

void SPFA()
{
    d[1][0]=0;  in[1][0]=1; q.push((Node){1,0});
    Node x;
    while(!q.empty())
    {
        x=q.front();    q.pop();
        int& u=x.poss;  int& time=x.time;   bool flag;
        in[u][time%k]=0;
        for(int i=fisrt[u];i!=-1;i=e[i].next)
        {
            int& v=e[i].to;
            int t=time; flag=0;
            while(nocan[t%k][u][v])
            {
                t++;
                if(t-time>k+1)
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                continue;
            if(t+1<d[v][t%k])
            {
                d[v][t%k]=t+1;
                if(!in[v][t%k])
                {
                    in[v][t%k]=1;
                    q.push((Node){v,t+1});
                }
            }
        }
        
    }
    for(int i=0;i<k;i++)
        ans=min(ans,d[n][i]);
    if(ans==INF)
        cout<<"No solution."<<endl;
    else
        cout<<ans<<endl;
}

int main()
{
    init();
    SPFA();
    return 0;
}
  • 0
    @ 2016-07-22 15:30:23

    扩展SPFA即可秒杀。SPFA时，到达每个点的最短时间被记录在数组 A 里（A 等价于最短路中的最小距离数组）。假设目前从队列取出的节点为 u，枚举与其相连的点 v，找出 u -> v 最快能在多久之后接通，然后依照规则更新。

    说一下注意事项：
    - 图是双向的
    - 第二个测试点 k=0，mod的时候要小心

    放一段代码

    for(v=1; v<=numV; v++){
    if(G[u][v]){ //若 u, v 之间联通
    if(cycle > 0){
    for(i=0; i<cycle; i++){ //找出多久之后没人巡逻
    if(!banned[(minTime[u]+i)%cycle][u][v])
    break;
    }
    if(!banned[(minTime[u]+i)%cycle][u][v] && minTime[v]>minTime[u]+i+1){ //更新
    minTime[v] = minTime[u]+i+1;
    if(!using[v]){
    using[v] = 1;
    queue[tail++] = v;
    }
    }
    }else{
    if(minTime[v] > minTime[u]+1){
    minTime[v] = minTime[u]+1;
    if(!using[v]){
    using[v] = 1;
    queue[tail++] = v;
    }
    }
    }
    }
    }

  • 0
    @ 2016-05-16 20:23:07

    BFS改造（重复入队）+散列
    c++
    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #define maxn 120
    #define maxk 15
    using namespace std;
    struct node{int t,inqn,nd;};
    struct check{int f,t;};
    vector<int> map[maxn];
    vector<check> ck[maxk];
    queue<node> que;
    int N,M,K,vis[maxn]={0};
    int jud(int time,int f,int t){
    time%=K;
    for(int i=0;i<ck[time].size();i++){
    if(ck[time][i].f==f && ck[time][i].t==t) return 0;
    }
    return 1;
    }
    int bfs(int T){
    int save;
    node tmp,enew;
    tmp.t=0,tmp.inqn=1,tmp.nd=T;
    que.push(tmp); vis[T]=1;
    while(!que.empty()){
    save=0;
    tmp=que.front(); que.pop(); //printf("%d %d %d\n",tmp.t,tmp.inqn,tmp.nd);
    if(tmp.nd==N)
    return tmp.t;//reach
    for(int i=0;i<map[tmp.nd].size();i++){
    if(jud(tmp.t,tmp.nd,map[tmp.nd][i]) && vis[map[tmp.nd][i]]==0){
    enew.t=tmp.t+1,enew.nd=map[tmp.nd][i],enew.inqn=1;
    que.push(enew);//go
    vis[map[tmp.nd][i]]=1;
    }else save=1;
    }
    if(save == 1 && tmp.inqn <= K){tmp.inqn++,tmp.t++; que.push(tmp);}//hide
    }
    return -1;
    }
    int main(){
    int f,t;
    node tmp; check tmpck;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
    scanf("%d%d",&f,&t);
    map[f].push_back(t);
    map[t].push_back(f);
    }
    scanf("%d",&K);
    for(int i=0;i<K;i++)
    while(scanf("%d%d",&f,&t) && (f!=0 && t!=0)){
    tmpck.f=f,tmpck.t=t;
    ck[i].push_back(tmpck);
    tmpck.f=t,tmpck.t=f;
    ck[i].push_back(tmpck);
    }//read
    f=bfs(1);
    if(f==-1)
    printf("No solution.\n");
    else printf("%d\n",f);
    return 0;
    }

  • 0
    @ 2014-11-04 17:57:11

    program p1089;
    var
    f:array[1..100,1..10] of longint;
    n,m:longint;
    sf:array[1..100,1..100,1..10] of boolean;
    loc:array[1..100,1..500] of byte;
    d:array[1..100] of integer;
    i,t,x,y,ans,k:longint;
    que1,que2:array[1..1001] of longint;
    vis:array[1..100,1..10] of boolean;
    procedure bfs;
    var
    i:longint;
    link,tail:longint;
    begin
    link:=1;
    tail:=1;
    que1[1]:=1;
    que2[1]:=1;
    while (que1[link]<n)and(link<=1000) do begin
    for i:=1 to d[que1[link]] do begin if sf[que1[link],loc[que1[link],i],que2[link]] then if not(vis[loc[que1[link],i],que2[link]]) then begin inc(tail); que1[tail]:=loc[que1[link],i]; que2[tail]:=que2[link]+1; if que2[tail]>k then que2[tail]:=1; f[que1[tail],que2[tail]]:=f[que1[link],que2[link]]+1; vis[que1[tail],que2[tail]]:=true; end; end; inc(que2[link]);
    if que2[link]>k then que2[link]:=1;
    if not(vis[que1[link],que2[link]]) then begin
    vis[que1[link],que2[link]]:=true; tail:=tail+1; que1[tail]:=que1[link]; que2[tail]:=que2[link]; dec(que2[link]); if que2[link]=0 then que2[link]:=k; f[que1[tail],que2[tail]]:=f[que1[link],que2[link]]+1; end; link:=link+1;
    end;
    ans:=f[que1[link],que2[link]];
    end;
    begin
    fillchar(vis,sizeof(vis),false);
    fillchar(sf,sizeof(sf),true);
    fillchar(d,sizeof(d),0);
    readln(n,m);
    for i:=1 to m do begin
    readln(x,y); d[x]:=d[x]+1; loc[x,d[x]]:=y; d[y]:=d[y]+1; loc[y,d[y]]:=x; end; readln(k);
    t:=1;
    while t<=k do begin
    readln(x,y); if (x=0)and(y=0) then t:=t+1 else begin sf[x,y,t]:=false; sf[y,x,t]:=false; end; end; bfs;
    if ans<=0 then writeln('No solution.')
    else writeln(ans); end.

  • 0
    @ 2014-10-04 10:22:00

    program vijos1089;
    var s,i,j,min,x1,y1,i1,k,m,n:longint;
    v:array[0..500,0..500]of boolean;
    a:array[0..10,0..600,0..600]of longint;
    f:array[0..50000]of longint;
    g:array[0..2000,0..2000]of longint;
    x,y:array[0..50000]of longint;
    procedure dfs(s,t,len,dd:longint);
    var i,j,o,l:longint;
    begin
    if (len>min)or(dd=k+1) then exit;
    if t=n then
    begin
    if len<min then
    begin
    min:=len;
    end;
    exit;
    end;
    if (k>0) then
    dfs(s+1,t,len+1,dd+1);
    if s>k then s:=s-k;
    for i:=1 to g[t,0] do
    if ((a[s,t,g[t,i]]=1)or(k=0))and(f[g[t,i]]>f[t]+1)and(v[t,g[t,i]]) then
    begin
    v[t,g[t,i]]:=false;
    v[g[t,i],t]:=false;
    o:=f[g[t,i]];
    f[g[t,i]]:=f[t]+1;
    dfs(s+1,g[t,i],len+1,0);
    f[g[t,i]]:=o;
    v[t,g[t,i]]:=true;
    v[g[t,i],t]:=true;
    end;
    end;
    begin
    fillchar(v,sizeof(v),true);
    readln(n,m);
    fillchar(f,sizeof(f),$7f);
    f[1]:=0;
    for i:=1 to m do
    begin
    readln(x[i],y[i]);
    inc(g[x[i],0]);g[x[i],g[x[i],0]]:=y[i];
    inc(g[y[i],0]);g[y[i],g[y[i],0]]:=x[i];
    end;
    readln(k);
    for i:=1 to k do
    for j:=1 to n do
    for i1:=1 to n do
    a[i,j,i1]:=1;
    s:=1;
    while s<=k do
    begin
    readln(x1,y1);
    if (x1=0)and(y1=0) then
    inc(s)
    else
    a[s,x1,y1]:=0;
    end;
    min:=maxlongint;
    dfs(1,1,0,0);
    if min<maxlongint then
    writeln(min)
    else
    writeln('No solution.');
    end.
    6 7 过不去;求改错.

  • 0
    @ 2014-07-09 23:23:45

    program p1089;
    var
    f:array[1..100,1..10] of longint;
    n,m:longint;
    sf:array[1..100,1..100,1..10] of boolean;
    loc:array[1..100,1..500] of byte;
    d:array[1..100] of integer;
    i,t,x,y,ans,k:longint;
    que1,que2:array[1..1001] of longint;
    vis:array[1..100,1..10] of boolean;
    procedure bfs;
    var
    i:longint;
    link,tail:longint;
    begin
    link:=1;
    tail:=1;
    que1[1]:=1;
    que2[1]:=1;
    while (que1[link]<n)and(link<=1000) do begin
    for i:=1 to d[que1[link]] do begin
    if sf[que1[link],loc[que1[link],i],que2[link]] then
    if not(vis[loc[que1[link],i],que2[link]]) then begin
    inc(tail);
    que1[tail]:=loc[que1[link],i];
    que2[tail]:=que2[link]+1;
    if que2[tail]>k then que2[tail]:=1;
    f[que1[tail],que2[tail]]:=f[que1[link],que2[link]]+1;
    vis[que1[tail],que2[tail]]:=true;
    end;
    end;
    inc(que2[link]);
    if que2[link]>k then que2[link]:=1;
    if not(vis[que1[link],que2[link]]) then begin
    vis[que1[link],que2[link]]:=true;
    tail:=tail+1;
    que1[tail]:=que1[link];
    que2[tail]:=que2[link];
    dec(que2[link]);
    if que2[link]=0 then que2[link]:=k;
    f[que1[tail],que2[tail]]:=f[que1[link],que2[link]]+1;
    end;
    link:=link+1;
    end;
    ans:=f[que1[link],que2[link]];
    end;
    begin
    fillchar(vis,sizeof(vis),false);
    fillchar(sf,sizeof(sf),true);
    fillchar(d,sizeof(d),0);
    readln(n,m);
    for i:=1 to m do begin
    readln(x,y);
    d[x]:=d[x]+1;
    loc[x,d[x]]:=y;
    d[y]:=d[y]+1;
    loc[y,d[y]]:=x;
    end;
    readln(k);
    t:=1;
    while t<=k do begin
    readln(x,y);
    if (x=0)and(y=0) then t:=t+1
    else begin sf[x,y,t]:=false; sf[y,x,t]:=false; end;
    end;
    bfs;
    if ans<=0 then writeln('No solution.')
    else writeln(ans);
    end.
    这题难度有3？？？建议设成2简单的判重+边储存

  • 0
    @ 2013-02-16 10:21:18

    点击查看程序源码+详细题解

  • 0
    @ 2012-10-11 11:38:29

    这个题呢可以用SPFA解决。每次需要扩展一个点的时候，对其的扩展结点进行判断，看看是否有人巡逻，如果有，那么等待，时间+1需要注意的是这个题全部都是双向边。还有注意一下，每次有人巡逻的时候时间+1需要继续判断，所以我是通过一个深搜来完成的。然后如果在一个点等着总是有人巡逻的话怎么办呢？那么我们进行判断，只要等待的时间>k的时候直接返回不能。就解决了。。。注意一下都是双向边。

    欢迎来我的间： http://hi.baidu.com/samroxas/item/7461ac59d3e838d9d48bacf7

    附代码：

    program vijos1089;

    var

    wait,time,x,now,n,m,k,a,b,total,i,sum,head,tail,next,nextt,y,temp:longint;

    map:array[1..100] of longint;

    save:array[1..1000,1..2] of longint;

    check:array[1..100,1..100] of longint;

    line:array[1..5000,1..2] of longint;

    dist,queue:array[1..100] of longint;

    flag:array[1..100] of boolean;

    procedure add(i,j:longint);

    begin

    inc(total);

    save[total,1]:=j;

    save[total,2]:=map[i];

    map[i]:=total;

    end;

    function deal(a,b,now:longint):longint;

    var

    y,temp,store:longint;

    begin

    if time>k then

    exit(-1);

    deal:=0;

    y:=check[a,b];

    while y-1 do

    begin

    temp:=now mod k;

    if temp=0 then

    temp:=k;

    if temp=line[y,1] then

    begin

    inc(time);

    store:=deal(a,b,now+1);

    if store=-1 then

    exit(-1);

    end;

    y:=line[y,2];

    end;

    end;

    begin

    readln(n,m);

    fillchar(map,sizeof(map),\(ff);
    fillchar(check,sizeof(check),\)ff);

    for i:=1 to m do

    begin

    readln(a,b);

    add(a,b);

    add(b,a);

    end;

    readln(k);

    for i:=1 to k do

    begin

    readln(a,b);

    while (a0) and (b0) do

    begin

    inc(sum);

    line[sum,1]:=i;

    line[sum,2]:=check[a,b];

    check[a,b]:=sum;

    inc(sum);

    line[sum,1]:=i;

    line[sum,2]:=check;

    check:=sum;

    readln(a,b);

    end;

    end;

    head:=0;

    tail:=1;

    queue[1]:=1;

    fillchar(dist,sizeof(dist),$7f);

    dist[1]:=0;

    flag[1]:=true;

    while headtail do

    begin

    head:=(head mod 100)+1;

    now:=queue[head];

    flag[now]:=false;

    x:=map[now];

    while x-1 do

    begin

    next:=save[x,1];

    nextt:=dist[now]+1;

    if k0 then

    begin

    time:=0;

    wait:=deal(now,next,nextt);

    if wait=-1 then

    break;

    nextt:=nextt+time;

    end;

    if nextt

  • 0
    @ 2012-07-12 11:22:14

    题目都没说是无向边好像。。。然后注意k的范围

  • 0
    @ 2009-11-08 23:17:22

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    认真分析题......

    注意在有的周期里哪条边都不能走......

  • 0
    @ 2009-10-30 08:55:02

    用类似SPFA的BFS过了，要注意一条边可能在不同周期内巡逻多次

  • 0
    @ 2009-10-09 09:32:46

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    o(╯□╰)o No solution 后面有一个点号。。。

  • 0
    @ 2009-10-08 12:01:27

    直接暴搜即可

    夏润神用bellman-ford，太牛逼了

  • 0
    @ 2009-06-14 22:04:39

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

  • 0
    @ 2009-02-17 18:30:22

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    用dfs+hash即可,hash[i,t mod k]用来记录到第i点第t mod k的最优值,注意remember躲藏.

  • 0
    @ 2009-02-08 14:05:01

    问一下：第二点的数据是什么？

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：运行超时...

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    No solution.的情况没有处理好 = =

  • 0
    @ 2009-02-03 19:04:55

    BFS+Hash=AC

    注意一下k=0的特殊情况。还有边是无向的。

小胖抗日

信息

ID
1089
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
819
已通过
171
通过率
21%
被复制
8
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1