题意：给n个点m条边，两个点间无重边，然后是m行的ui，vi，wi代表起始点和边的权重（第几个代表第几条边）然后在给起始点u，问选哪些边，可以满足从起始点u到达其它点距离最短，且使整张图的权重最小;
输出：所有边的总权重 以及选的边（递增顺序，若答案多组，输出任意一组）
思路：spfa，就是在更新每个点的最短路是，顺便记录和更新连到这个点的最短边;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>
#define ll long long
#define INF 0x3f3f3f3f using namespace std;
const int MAXN = ;
ll total,head[MAXN],dis[MAXN],used[MAXN];
struct nodes
{
ll e,l,next,th;
} edge[MAXN];
struct nodes2
{
ll s,dis,p;
bool operator <(nodes2 q) const
{
return dis > q.dis;
}
} cur;
void add(ll x,ll y,ll l,ll th)
{
edge[total].e = y;
edge[total].l = l;
edge[total].th = th;
edge[total].next = head[x];
head[x] = total++;
}
void init( )
{
total = ;
memset(head,-,sizeof(head));
memset(used,-,sizeof(used));
fill(dis,dis+,INF);
} void spfa(int x,int n)
{
ll s,e,subdis,th;
priority_queue<nodes2>Q;
cur.dis = ,cur.s = x;
dis[x] = ;
Q.push(cur);
while(!Q.empty())
{
cur = Q.top();
Q.pop();
s = cur.s;
for(int i = head[s]; i != -; i = edge[i].next)
{
subdis = edge[i].l,e = edge[i].e,th = edge[i].th;
if(dis[e] > dis[s] + subdis)
{
dis[e] = dis[s] + subdis;
used[e] = th;
cur.s = edge[i].e,cur.dis = dis[e];
Q.push(cur);
}
}
}
ll d=;
for(int i = ; i <= n; i++)
d += dis[i];
printf("%lld\n",d);
sort(used,used+n);
for(int i = ; i< n; i++)
if(i != n)
printf("%lld ",used[i]);
else
printf("%lld\n",used[i]);
}
int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
init();
for(int i = ; i <= m; i++)
{
ll x,y,l;
scanf("%lld %lld %lld",&x,&y,&l);
add(x,y,l,i);
add(y,x,l,i);
}
int s;
scanf("%d",&s);
spfa(s,n);
return ;
}