T . Ideal Path
题目就是说给一个n,和一个m,起始点在1,问从1到n的最短路径长度和在此过程中最小的颜色序号。
有m行,表示a,b,联通并且颜色为c;
可以先从n点出发,bfs找出每个点相对n的最短距离,再从起始点出发bfs并判断最短颜色序。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100005;
int n,m;
int tol;
int head[maxn];
int vis[maxn];
int d[maxn];
vector<int>ans;
queue<int >que;
queue<int >que2;
queue<int>tmp;
queue<int>tmp1;
struct Edge {
int v,nxt,w;
} edge[maxn*4];
int main() {
while(cin>>n>>m) {
tol=0;
memset(head,-1,sizeof(head));
for(int i=1; i<=m; ++i) {
ll u,v,w;
cin>>u>>v>>w;
edge[tol].v=v;
edge[tol].w=w;
edge[tol].nxt=head[u];
head[u]=tol++;
swap(v,u);
edge[tol].v=v;
edge[tol].w=w;
edge[tol].nxt=head[u];
head[u]=tol++;
}
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
queue<int>que;
que.push(n);
vis[n]=1;
d[n]=0;
while(!que.empty()) {
int u=que.front();
que.pop();
for(int i=head[u]; i!=-1; i=edge[i].nxt) {
int v=edge[i].v;
if(vis[v])continue;
vis[v]=1;
d[v]=d[u]+1;
que.push(v);
}
}
ans.clear();
memset(vis,0,sizeof(vis));
que.push(1);
vis[1]=1;
while(!que.empty()) {
int min_color=1000000000;
while(!que.empty()) {
int t=que.front();
que.pop();
tmp.push(t);
tmp1.push(t);
}
while(!tmp.empty()) {
int u=tmp.front();
tmp.pop();
if(u==n)break;
for(int i=head[u]; i!=-1; i=edge[i].nxt) {
int v=edge[i].v;
if(d[v]==d[u]-1) {
min_color=min(min_color,edge[i].w);
}
}
}
ans.push_back(min_color);
while(!tmp1.empty()) {
int u=tmp1.front();
tmp1.pop();
for(int i=head[u]; i!=-1; i=edge[i].nxt) {
int v=edge[i].v;
if(d[v]==d[u]-1&&!vis[v]&&edge[i].w==min_color) {
if(v==n)break;
vis[v]=1;
que2.push(v);
}
}
}
if(que.empty()) {
while(!que2.empty()) {
int t=que2.front();
que2.pop();
que.push(t);
}
}
}
printf("%d\n", ans.size());
printf("%d", ans[0]);
for(int i = 1; i < ans.size(); i++)
printf(" %d", ans[i]);
printf("\n");
}
return 0;
}