竹園論壇

標題: d243 - 圖論專家 [打印本頁]

作者: Sylveon 時間: 2014-5-9 13:08
標題: d243 - 圖論專家
原題：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());
}
}
}

}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)