codeforces545E – Paths and Trees(最短路)

题目链接：Paths and Trees

【题意】给出一张无向连通图，求点u到所有点最短路不变的情况下的最小生成树；

【分析】一开始往最小树形图想，可是会超时，果断不会了。其实在连通图上的一点出发到所有点的最短路就是一颗生成树(看来还没完全理解最短路)，然而只要在求最短路的时候让每条边的权值尽量小即可。用了spfa做。

【AC CODE】451ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int MAXN = 300000+10, MAXM = 300000*2+10;
int head[MAXN], tol, nxt[MAXM], to[MAXM], c[MAXM];

inline void add_edge(int u, int v, int cost)
{
    nxt[tol] = head[u], to[tol] = v, c[tol] = cost;
    head[u] = tol++;
}
bool inq[MAXN];
LL dis[MAXN];
int fre[MAXN];
void spfa(int st)
{
    queue<int> q;
    q.push(st);
    inq[st] = true;
    clc(dis,0x3f);
    dis[st] = 0;
    while(!q.empty())
    {
        int u = q.front();q.pop();
        inq[u] = false;
        for(int i = head[u]; ~i; i= nxt[i])
        {
            int v = to[i];
            if(dis[v] > dis[u]+c[i])
            {
                dis[v] = dis[u]+c[i];
                fre[v] = i;
                if(!inq[v])
                {
                    q.push(v);
                    inq[v] = true;
                }
            }
            else if(dis[v] == dis[u]+c[i] && c[i] < c[fre[v]])
            {
                fre[v] = i;
                /*if(!inq[v])
                {
                    q.push(v);
                    inq[v] = true;
                }*/
            }
        }
    }
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int n,m;
    scanf("%d %d%*c", &n,&m);
    clc(head,-1);
    tol = 0;
    rep(i,0,m)
    {
        int u,v,cost;
        scanf("%d %d %d%*c", &u, &v, &cost);
        add_edge(u,v,cost);
        add_edge(v,u,cost);
    }
    int st;
    scanf("%d\n", &st);
    spfa(st);
    LL sum = 0;
    repe(i,1,n)
    {
        if(i != st)
            sum += c[fre[i]];
    }
    printf("%I64d\n", sum);
    repe(i,1,n)
    {
        if(i == st) continue;
        printf("%d ", fre[i]/2+1);
    }
    putchar('\n');
    return 0;
}