题目描述
找到从1到n的最短路径,给定k个三元组作为条件,路径中不能出现三元组(难点)。
输入格式
输入文件第一行有三个数 N,M,K,意义如题目所述。接下来 M 行每行两个数 A,B,表示 A,B 间有一条边。再下面 K 行,每行三个数 ((A,B,C) 描述一个三元组。
输出格式
输出文件共两行数,第一行一个数S 表示最短路径长度。 。
第二行 S+1 个数,表示从 1 到 N 所经过的节点。
样例
输入:
4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4
输出:
4
1 3 2 3 4
算法1
(BFS) $O(m)$
记录路径,用bfs方便;
队列多加一个值记录上一个访问点
p数组防止多次访问同一条边
q用map存查找时O(log k)复杂度
时间复杂度
参考文献
C++ 代码
const int N = 3000 + 10;
int n,m,k;
vector<int> e[N];
map<pair<pair<int,int>,int>,int> q;
int p[N][N];
void solve()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1;i<=k;i++){
int x,y,z;
cin>>x>>y>>z;
q[{{x,y},z}]=1;
}
queue<pii> qu;
qu.push({1,1});
pii ans={-1,-1};
while(qu.size()){
int u=qu.front().first,v=qu.front().second;qu.pop();
if(v==n){
ans={u,v};
break;
}
for(auto ed:e[v]){
if(p[v][ed]||q.count({{u,v},ed})) continue;
p[v][ed]=u;
qu.push({v,ed});
}
}
if(ans==pii(-1,-1)) cout<<-1<<endl;
else{
int u=ans.first,v=ans.second;
vector<pii> path;
while(u!=1){
path.push_back({u,v});
int tmp=v;
v=u;
u=p[u][tmp];
}
path.push_back({1,v});
cout<<path.size()<<endl;
cout<<1<<' ';
for(int i=path.size()-1;i>=0;i--){
cout<<path[i].second<<' ';
}
}
}