POJ-3635-Full Tank?-spfa+ 우선 순위 큐
그리고 dij 달리기 그림을 사용하면 됩니다. 그리고 우선 대기열 최적화를 추가합니다.
한 점에 도달하지 못했을 때는 두 가지 선택이 있는데, 하나는 기름을 조금도 넣지 않고 뒤로 달리는 것이다.
다른 하나는 1리터의 기름을 넣는 것이다.
우선 대기열로 가장 좋은 하위 결과를 선택하십시오.
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
#define maxeg 10000
#define maxpt 1100
#define INF 99999999
struct lists
{
int u;
int v;
int w;
int next;
}node[maxeg*2+100];
int head[maxpt];
int nums;
void init()
{
memset(head,-1,sizeof(head));
nums=0;
}
void add(int u,int v,int w)
{
node[nums].u=u;
node[nums].v=v;
node[nums].w=w;
node[nums].next=head[u];
head[u]=nums++;
}
int vals[maxpt];
int n,m;
int d[maxpt][maxpt];
struct ns
{
int x;
int cc;
int val;
friend bool operator < (ns a,ns b)
{
return a.val>b.val;
}
}p,q;
priority_queue<ns>que;
void spfa(int cc,int st,int ed)
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=cc;j++)d[i][j]=INF;
}
d[st][0]=0;
while(!que.empty())que.pop();
p.cc=0;
p.x=st;
p.val=0;
que.push(p);
while(!que.empty())
{
q=que.top();
que.pop();
int u=q.x;
int c=q.cc;
int vv=q.val;
// cout<<u<<" "<<c<<" "<<vv<<endl;
if(u==ed)break;
//if(u==ed)continue;
for(i=head[u];i!=-1;i=node[i].next)
{
int v=node[i].v;
int w=node[i].w;
if(c>=w)
{
int yu=c-w;
if(d[v][yu]>d[u][c])
{
d[v][yu]=d[u][c];
p.x=v;
p.cc=yu;
p.val=d[v][yu];
que.push(p);
}
}
}
if(c<cc)
{
p.x=q.x;
p.cc=q.cc+1;
p.val=q.val+vals[u];
if(d[u][p.cc]>p.val)
{
d[u][p.cc]=p.val;
que.push(p);
}
}
}
int ans=INF;
for(i=0;i<=cc;i++)
{
ans=min(d[ed][i],ans);
}
if(ans!=INF)cout<<ans<<endl;
else cout<<"impossible"<<endl;
}
int main()
{
int i,a,b,c,q,s,t;
cin>>n>>m;
for(i=0;i<n;i++)scanf("%d",&vals[i]);
init();
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
scanf("%d",&q);
while(q--)
{
scanf("%d%d%d",&c,&s,&t);
spfa(c,s,t);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.