图论基础题。但是想偏了想了半天。
考虑先对原图做一次 tarjan 求割边。处理 \(c=1\) 的答案。
\(c=2\) 最自然的想法是枚举所有边，断掉，再重新跑 tarjan。但是会超时。但是不难发现，只有 tarjan 建出的 dfs 树上的树边删去时，树的形态有可能改变。
这些边有 \(O(n)\) 个，每个 \(O(n+m)\) 暴力跑。否则拿一个可重集，维护每个点返祖边所指向的点的 dfn，每次删去 \((u,v)\) 边时修改此集合，再 \(O(n)\) 对 dfs 树做一遍 dfs 处理出 tarjan 的 low 即可。
总时间复杂度 \(O(nm)\) 轻松过。
code：
点击查看代码
int n,m,s,t;
int cur,dfn[N],low[N],fa[N];
bool pd[M],vis[M];
multiset<int> st[N];vector<int> g[N],cut;
int tot=1,head[N];
struct node{int to,nxt,cw;}e[M<<1];
il void add(int u,int v,int w){e[++tot]={v,head[u],w},head[u]=tot;}
void pretar(int u,int f){
dfn[u]=low[u]=++cur,fa[u]=f;
go(i,u){
int v=e[i].to;
if(!dfn[v]){
pd[i/2]=1,g[u].eb(v);
pretar(v,i),low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])cut.eb(i/2);
}else if(i!=(f^1))low[u]=min(low[u],dfn[v]),st[u].insert(dfn[v]);
}
}
void dfs(int u,int f){
low[u]=++cur;
for(int v:g[u]){
dfs(v,u),low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])cut.eb(fa[v]/2);
}
low[u]=min(low[u],*st[u].begin());
}
void tarjan(int u,int f){
dfn[u]=low[u]=++cur,fa[u]=f;
go(i,u){
int v=e[i].to;
if(e[i].cw==-1)continue;
if(!dfn[v]){
tarjan(v,i),low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])cut.eb(i/2);
}else if(i!=(f^1))low[u]=min(low[u],dfn[v]);
}
}
il void init(){mems(low,0),cur=0,cut.clear();}
void Yorushika(){
scanf("%d%d%d%d",&n,&m,&s,&t);
rep(i,1,m){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add(u,v,w),add(v,u,w);
}
pretar(s,0);
if(!dfn[t])return puts("0\n0"),void();
int u=t;
while(u!=s){
vis[fa[u]/2]=1;
u=e[fa[u]^1].to;
}
int ans=(int)2e9+1,a=-1,b=-1;
for(int i:cut)if(vis[i]&&e[i*2].cw<ans)ans=e[i*2].cw,a=i,b=0;
for(int i=2;i<=tot;i+=2){
int u=e[i].to,v=e[i^1].to;
if(pd[i/2])continue;
st[u].erase(st[u].find(dfn[v])),st[v].erase(st[v].find(dfn[u]));
init(),dfs(s,0);
for(int j:cut)if(vis[j]&&e[i].cw+e[j*2].cw<ans)ans=e[i].cw+e[j*2].cw,a=i/2,b=j;
st[u].insert(dfn[v]),st[v].insert(dfn[u]);
}
for(int i=2;i<=tot;i+=2){
int u=e[i].to,v=e[i^1].to;
if(!pd[i/2])continue;
int tmp=e[i].cw;
e[i].cw=e[i^1].cw=-1;
init(),mems(fa,0),mems(dfn,0);
tarjan(s,0);
mems(vis,0),e[i].cw=e[i^1].cw=tmp;
if(!dfn[t])continue;
int p=t;
while(p!=s){
vis[fa[p]/2]=1;
p=e[fa[p]^1].to;
}
for(int j:cut)if(vis[j]&&e[i].cw+e[j*2].cw<ans)ans=e[i].cw+e[j*2].cw,a=i/2,b=j;
}
if(a==-1)puts("-1");
else if(!b)printf("%d\n1\n%d\n",ans,a);
else printf("%d\n2\n%d %d\n",ans,a,b);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}