[JLOI 2011] 코스
1817 단어 최 단 로
알고리즘:
우 리 는 dis [i] [j] 를 설치 하여 t 에서 i 까지 의 길 을 표시 하고 j 차 비행기 에 탑승 하 는 최소 비용 을 표시 하 였 으 며, 이어서 우 리 는 SPFA 를 이용 하여 상 태 를 이전 하면 된다.
답 은 max {dis [t] [i] (0 < = i < = k)} 입 니 다.(k 가 경로 의 개수 보다 클 수 있 음 을 고려 합 니 다.)
Code:
#include
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
template void read(T &num){
char c=getchar();num=0;T f=1;
while(c'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
num*=f;
}
template void qwq(T x){
if(x>9)qwq(x/10);
putchar(x%10+'0');
}
template void write(T x){
if(x<0){x=-x;putchar('-');}
qwq(x);putchar('
');
}
template void chkmin(T &x,T y){x=x > >v;
int dis[10010][15];bool in[10010][15];
inline void SPFA(){
rep(i,1,n){
rep(j,0,k){dis[i][j]=INT_MAX;}
}
v.push(make_pair(0,make_pair(s,0)));in[s][0]=1;dis[s][0]=0;
while(!v.empty()){
int nop1=v.top().second.first;int nop2=v.top().second.second;
in[nop1][nop2]=0;v.pop();
for(int i=head[nop1];i;i=edge[i].nxt){
int temp=edge[i].vertice;
if(dis[nop1][nop2]+edge[i].w
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1233 또는 원활 한 공정 최소 생 성 트 리 (prim 알고리즘 + kruskal 알고리즘)그럼 이 연결 서브 맵 은 G 의 최소 생 성 트 리 입 니 다.최소 생 성 트 리 를 구 하 는 흔 한 알고리즘 은 Prim 알고리즘 입 니 다. 욕심 전략 을 사용 하기 때문에 집합 S 에 새로운 정점 을 추가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
