POJ 3159 Candies (차동 제약 시스템)
사고방식: 원래 SPFA + 핸드폰 대기 열 TLE 였 는데 토론 용 창 고 를 보면 돼 -!(손 으로 쓸 때 f1 + +, – f1)
#include<map>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int mod=100000000;
bool vis[150010];
int head[150010],cnt,dis[150010],qu[150010*4];
struct node
{
int to,c,next;
}q[150010*4];
int n;
void add(int a,int b,int c){
q[cnt].to=b;
q[cnt].c=c;
q[cnt].next=head[a];
head[a]=cnt++;
}
void SPFA(){
for(int i=1;i<=n;i++){
dis[i]=inf;
vis[i]=false;
}
int f1;
f1=0;
//stack<int>qq;
qu[f1++]=1;
//qq.push(1);
dis[1]=0;
vis[1]=true;
while(f1>0){
//int u=qq.top();
//qq.pop();
int u=qu[--f1];
vis[u]=false;
for(int i=head[u];~i;i=q[i].next){
int v=q[i].to;
if(dis[v]>dis[u]+q[i].c){
dis[v]=dis[u]+q[i].c;
if(!vis[v]){
vis[v]=true;
//qq.push(v);
qu[f1++]=v;
}
}
}
}
}
int main(){
int m,i,j,k;
while(~scanf("%d%d",&n,&m)){
int a,b,c;
cnt=0;
memset(head,-1,sizeof(head));
for(i=0;i<m;++i){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
SPFA();
printf("%d
",dis[n]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.