CodeForces - 1407E Egor in the Republic of Dagestan(최단 루트+dp)

2730 단어 최단로동적 기획CodeForces 상단
제목 링크: 클릭하여 보기
제목 대의: n개의 점과 m개의 유방향도를 제시하고 각 변의 길이는 1이며 하나의 속성은 0이나 1로 표시된다. 현재 각 노드에 값을 부여해야 한다.
  • 점 u의 권한이 0이면 u는 (u, v)만 갈 수 있고 이 변의 속성이 0인 변
  • 점 u의 권한이 1이면 u는 (u, v)만 갈 수 있고 이 변의 속성은 1의 변
    • 점 1에서 점 n까지의 최단로를 어떻게 할당하여 구조 방안을 출력할 수 있는지 묻다
    제목 분석: 먼저 dp를 설계한다. 최단로의 템플릿에 부합하기 위해 이 제목에서 나는 d수조를 dp수조로 한다. d[i]와 d[i][1]는 각각 i점이 0이나 1일 때 도착점 n의 최단로를 나타낸다. 분명히 d[i]와 d[i]의 크기를 비교하고 비교적 큰 것을 점 i로 선택하면 최단로를 가장 크게 할 수 있다. 둘이 같을 때 부치는 0이나 1이 똑같다.
    그리고 dp의 이동을 고려한다. 왜냐하면 우리는 n개의 점을 기점으로 하는 d[i]와 d[i]를 요구하기 때문에 n번의 디제스트라를 구할 수 없을 것이다. 그리고 모든 d수조는 점 n을 종점으로 하기 때문에 우리는 전체 그림을 뒤집은 다음에 점 n을 기점으로 하는 단원 최단로를 구하는 것도 괜찮다.
    다음은 어떻게 상태 방정식을 옮겨야 하는지 설명해 드리겠습니다. 만약에 지금 u에서 v로의 변이 있고 이 변의 속성은 t입니다. 우리는 최단로를 가장 크게 해야 하기 때문에 분명히 max(d[u]0], d[u]1])로 점 v로 옮겨야 합니다. 이것은 가장 간단한 최단거리 문제입니다. 이 제목의 변권이 모두 1이기 때문에 우리는 bfs로 디제스트라를 대체할 수 있습니다.
    한 가지 주의해야 할 것은 각 점마다 두 가지 속성이 갱신되어야 하기 때문에 각 점은 여러 번 누적될 수 있다. 만약에 일반 디제스트라처럼 비스 제한을 가하면 답이 틀릴 수 있기 때문에 우리는 다른 방법으로 제약을 하고 코드 실현에 주석을 달 수 있다. 그 효과는 비스 표시의 효과와 같다.
    마지막 답은 분명히 max(d[1]0], d[1])입니다. 방안은 구한 수조에 따라 직접 구성하면 됩니다.
    코드:
    #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
 
typedef long long LL;
 
typedef unsigned long long ull;
 
const int inf=0x3f3f3f3f;

const int N=5e5+100;

vector>node[N];

int dis[N][2],n,m;

void bfs()
{
	memset(dis,inf,sizeof(dis));
	dis[n][0]=dis[n][1]=0;
	queue>q;
	q.push(make_pair(n,0));
	while(q.size())
	{
		int u,w;
		tie(u,w)=q.front();
		q.pop();
		if(max(dis[u][0],dis[u][1])!=w)//    vis    
			continue;
		for(auto t:node[u])
		{
			int v=t.first;
			int type=t.second;
			if(dis[v][type]>max(dis[u][0],dis[u][1])+1)
			{
				dis[v][type]=max(dis[u][0],dis[u][1])+1;
				q.push(make_pair(v,max(dis[v][0],dis[v][1])));
			}
		}
	}
}
 
int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		node[v].emplace_back(u,c);
	}
	bfs();
	int ans=max(dis[1][0],dis[1][1]);
	if(ans==inf)
		ans=-1;
	printf("%d
    ",ans);
	for(int i=1;i<=n;i++)
		if(dis[i][0]>=dis[i][1])
			putchar('0');
		else
			putchar('1');

















	return 0;
}

    기능 소개
    Firebase Firestore의 Flutter ListView

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage