이 문제는 5번째로 많이 풀린 문제로 18팀이 풀었습니다.
Tianjin University의 TJU_HanoiTower팀이 35분만에 최초로 풀었네요.
(36분에는 제가 속한 팀이..^^)
푼 팀의 수나 최초로 풀린 시간으로 볼 때, 그리 어려운 문제는 아니었습니다.
다만 H번이라 배치가 뒤에 되어 있어서 놓치기 쉬웠을 뿐이지요.
간략히 문제 설명을 해드리자면,
무방향 무가중치 그래프가 하나 주어집니다

그리고 path가 하나 주어집니다.
[1 2 2 7 5 5 5 7 4]
path는 이동 가능한 길일 수도 있고, 중간에 이동이 불가능할 수도 있습니다.
path에 각 숫자를 바꿔서 이동이 가능한 path로 바꾸는데,
바꾼 숫자의 개수를 최소로 하면 몇이 되냐는 게 문제입니다.
예제의 경우에 답은 1이고, 아래와 같은 3가지 방법이 가능합니다.
[1 2 2 4 5 5 5 7 4]
[1 2 4 7 5 5 5 7 4]
[1 2 2 6 5 5 5 7 4]
그래프의 버텍스 개수는 최대 100개이고, 에지 개수는 최대 4950개, path의 길이는 최대 200입니다.
[spoiler="답 보기..."] 이 문제는 간단한 DP 문제입니다.
그래프의 버텍스 개수를 n, path의 길이를 L이라고 하면 아래처럼 풀 수 있습니다.

• 정의 - 0 <= i < L , 0 <= j < n dy[i][j] = path의 i번째 버텍스를 j번 버텍스로 정했을 때 (바꿨을 때 or 유지했을 때) 얻을 수 있는 최적해
• 점화식 - j가 path의 i번째 버텍스라면 c=0 , 아니라면 c=1 j번 버텍스에서 k번 버텍스로 이동 가능 (k=j인 경우도 이동 가능), 0 <= k < n dy[i][j] = min(dy[i-1][k]+c)
• 초기화 - dy[0][j] = path의 첫번째 버텍스가 j라면 0 , 아니라면 1
• 시간복잡도 - O(L * n^2) ~~~ cpp

#include
#include
#include
using namespace std;
#define FOR(i,a,b) for( int i=(a); i<(b); ++i)
#define REP(i,n) for(int i=0; i<(n); ++i)
int n,m;
int dt[101][101],dy[201][101];
int L,pt[201];
int main()
{
int tn;
cin>>tn;
while (tn--) {
cin>>n>>m;
memset(dt,0,sizeof(dt));
REP(i,m) {
int a,b;
cin>>a>>b;
a--,b--;
dt[a][b]=dt[b][a]=1;
}
REP(i,n) dt[i][i]=1;
cin>>L;
REP(i,L) {
cin>>pt[i];
pt[i]--;
}
memset(dy,63,sizeof(dy));
REP(i,n) dy[0][i]=(pt[0]==i) ? 0 : 1;
FOR(i,1,L)
REP(j,n) {
int c=(pt[i]==j) ? 0 : 1;
REP(k,n) if (dt[j][k])
dy[i][j]=min(dy[i][j],dy[i-1][k]+c);
}
int mn=234234234;
REP(i,n) mn=min(mn,dy[L-1][i]);
cout<<mn<<endl;
}
return 0;
}

소문자 l이랑 숫자 1이랑 코드에서 전혀 구분이 안되네요.. 대문자로 바꿨습니다..
[/spoiler]<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/53918">원문보기</a>]</div>