d243 - 圖論專家

Sylveon

原題：http://zerojudge.tw/ShowProblem?problemid=d243
AC：http://zerojudge.tw/Submissions? ... mp;account=lfs92002

用A*直接過

/**********************************************************************************/
/*  Problem: d243 "圖論專家" from                                             */
/*  Language: CPP (1584 Bytes)                                                    */
/*  Result: AC(4ms, 344KB) judge by this@ZeroJudge                                */
/*  Author: lfs92002 at 2013-07-27 18:17:01                                       */
/**********************************************************************************/


#include<cstdio>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;

int d[200];
void init(int N)
{
        for(int i=0;i<N;++i)
                d[i]=i;
}
int lead(int a)
{
        if(d[a]==a)return a;
        return d[a]=lead(d[a]);
}
bool same(int a,int b)
{
        return lead(a)==lead(b);
}
void U(int a,int b)
{
        d[lead(a)]=lead(b);
}

struct node
{
        int e,w;
};
inline bool operator<(const node &a,const node &b)
{
        return a.w>b.w;
}
vector<node> V[100];
int N,M,s,t,w,P,k,c=1;
int dist[101];
int count[101];
priority_queue<node> pq;
int astar()
{
        while(!pq.empty())
                pq.pop();
        memset(dist,0x7f,sizeof(dist));
        memset(count,0,sizeof(count));
        pq.push((node){s,0});
        while(!pq.empty())
        {
                node n=pq.top();
                pq.pop();
                if(dist[n.e]!=n.w)
                {
                        dist[n.e]=n.w;
                        count[n.e]++;
                        if(n.e==t && count[n.e]==k)return dist[n.e];
                        for(vector<node>::iterator it=V[n.e].begin();
                                it!=V[n.e].end();
                                ++it)
                        {
                                pq.push((node){it->e,dist[n.e]+it->w});
                        }
                }
        }
}
int main()
{
       
        while(~scanf("%d%d",&N,&M))
        {
                init(200);
                for(int i=0;i<N;++i)
                        V[i].clear();
                for(int i=0;i<M;++i)
                {
                        scanf("%d%d%d",&s,&t,&w);
                        V[s].push_back((node){t,w});
                        V[t].push_back((node){s,w});
                        U(s,t);
                }
                scanf("%d",&P);
                printf("Set #%d\n",c++);
                while(P--)
                {
                        scanf("%d%d%d",&s,&t,&k);
                        if(!same(s,t))
                        {
                                puts("?");
                        }
                        else if(s==t&&V[s].size()==0)
                        {
                                if(k>1)
                                puts("?");
                                else
                                puts("0");
                        }
                        else
                        {
                                printf("%d\n",astar());
                        }
                }
        }
       
}