题目链接：http://codeforces.com/problemset/problem/1204/C
给定一组序列，P1,P2,P3...Pm，这是一组合法路径的序列，即任意的Pi和Pi+1之间有边相连，求一组新的序列V，V为原序列P的子集（通过删除P中某些元素获得）， 且顺序遍历V序列中的各个顶点时，P序列这组路径是遍历所有V序列顶点的最短路径，输出V序列元素的个数和V序列各个元素。
思路：首先floyd计算各个顶点相互之间到达的最短路径dist[ i ] [ i+1 ](i到i+1的最短路) ，设cur为目前放入所求答案序列的最后一个元素，开始遍历P序列的元素，设目前遍历到的元素是P[ i ]，如果cur按照P序列中的元素顺序走到 P[ i ] 的距离 > dist [ cur ] [ i ]，则说明按照cur 在P中，顺序遍历各个元素到P[ i ] 所走的是最短路径，但是因为经过 P[ i -1 ]到P[ i ]，才使得 其小于cur到P[ i ]的最短路，所以如果按照dist[cur][ P[ i ] ]这条路走，就不会经过P[ i-1 ]，这就不符合P序列的遍历顺序，为了经过P[ i-1 ]，我们把P[ i-1 ]放入V中，替换 cur = P [ i -1 ] ，依次类推不断更新直到最后一个元素。
具体看AC代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define maxn 105
#define inf 0x3f3f3f3f
using namespace std;
vector<string> g;
vector<int> ans;
int dist[maxn][maxn];
int p[1000005];
int n,m,dis,cur;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j]=min(dist[i][j],dist[i][k] + dist[k][j]);
}
}
}
}
int main(){
cin>>n;
for(int i = 0;i<n;i++){
string t;
cin>>t;
g.push_back(t);
}
memset(dist,inf,sizeof(dist));
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(g[i][j] == '1'){
dist[i+1][j+1] = 1;
}
if(i==j){
dist[i+1][j+1] = 0;
}
}
}
floyd();
cin>>m;
for(int i = 1;i<=m;i++){
cin>>p[i];
}
ans.push_back(p[1]);
cur = p[1],dis = 0;
for(int i = 2;i<=m;i++){
dis+=dist[p[i-1]][p[i]];
if(dis > dist[cur][p[i]]){
ans.push_back(p[i-1]);
cur = p[i-1];
dis = dist[cur][p[i]];
}
}
ans.push_back(p[m]);
cout<<ans.size() <<endl;
for(int i = 0;i<ans.size() ;i++){
if(i){
cout<<" "<<ans[i];
}
else{
cout<<ans[i];
}
}
return 0;
}