题目链接：http://codeforces.com/contest/1076/problem/D
题意：给一个n个点,m条边的无向图。要求保留最多k条边，使得其他点到1点的最短路剩余最多。
思路：当找到单源最短路后，将其转换为一个所有点到点1都是最短路的树状结构，利用贪心确定所要保留的K条边（找离根最近的边，利用BFS）。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#define ll long long
//#define local using namespace std; const int MOD = 1e9+;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 3e5 + ;
const int maxedge = 3e5 + ; struct qnode {
int v;
ll c;
qnode(int v=,ll c=) : v(v), c(c) {}
bool operator < (const qnode &r)const {//priority_queue 默认从大到小排列
return c > r.c;
}
}; struct Edge {
int v, w, pre;
} edge[maxedge*]; int point[maxn]; //point[i] = -1
int cnt;
bool vis[maxn]; // already init in the dijkstra
ll dist[maxn]; // already init in the dijkstra, overflow!
vector <int> v1[maxn];
vector <int> v2[maxn];
struct Path {
int u, e;
}path[maxn]; void AddEdge(int u, int v, int w) {
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].pre = point[u];
point[u] = cnt++;
} void Dijkstra(int n,int start) {
memset(vis,false,sizeof(vis));
memset(dist, 0x3f, sizeof(dist));
priority_queue <qnode> que;
while(!que.empty()) que.pop();
dist[start] = ;
que.push(qnode(start, ));
qnode tmp;
while(!que.empty()) {
tmp = que.top(); que.pop();
int u = tmp.v;
if(vis[u]) continue;
vis[u] = true;
for(int i = point[u]; i != -; i = edge[i].pre) {
int v = edge[i].v;
int w = edge[i].w;
if(!vis[v] && dist[v]>dist[u]+w) {
dist[v] = dist[u]+w;
que.push(qnode(v, dist[v]));
path[v].u = u;
path[v].e = i;
}
}
}
} void init() {
cnt = ;
memset(point, -, sizeof(point));
} int main() {
#ifdef local
if(freopen("/Users/Andrew/Desktop/data.txt", "r", stdin) == NULL) printf("can't open this file!\n");
#endif int n, m, k;
scanf("%d%d%d", &n, &m, &k);
init();
for (int i = ; i < m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
AddEdge(u, v, w);
AddEdge(v, u, w);
}
Dijkstra(n, );
for (int i = ; i <= n; ++i) {
v1[path[i].u].push_back(i);
v2[path[i].u].push_back(path[i].e);
}
queue<int> q;
q.push();
int ans = ;
int Ans[maxn];
while (q.size()) {
int tmp = q.front();
q.pop();
for (int j = ; j < v1[tmp].size() && ans < k; ++j) {
q.push(v1[tmp][j]);
Ans[ans++] = v2[tmp][j]/;
}
}
printf("%d\n", ans);
for (int i = ; i < ans; ++i) {
if (i)
printf(" %d", Ans[i]+);
else printf("%d", Ans[i]+);
}
printf("\n");
#ifdef local
fclose(stdin);
#endif
return ;
}