Codeforces Round #303 (Div. 2) - c++编程基础

TOP

Codeforces Round #303 (Div. 2)(二)

2015-11-21 01:01:26 来源: 作者: 【大中小】浏览:4次

55秒 ************************************************************************/ #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair PLL; static const int N = 300100; LL d[N]; bool flag[N]; bool vis[N]; int head[N]; int cost[N]; int tot; int use[N]; vector ans; priority_queue < PLL, vector , greater > qu; struct node { int w; int id; int nxt; int to; }edge[N << 1]; void addedge(int u, int v, int w, int id) { edge[tot].to = v; edge[tot].w = w; edge[tot].nxt = head[u]; edge[tot].id = id; head[u] = tot++; } void Dijkstra(int s) { d[s] = 0; cost[s] = 0; memset(flag, 0, sizeof(flag)); memset(vis, 0, sizeof(vis)); while (!qu.empty()) { qu.pop(); } qu.push(make_pair(d[s], s)); while (!qu.empty()) { PLL tmp = qu.top(); qu.pop(); int u = tmp.second; LL dist = tmp.first; if (flag[u]) { continue; } flag[u] = 1; vis[use[u]] = 1; for (int i = head[u]; ~i; i = edge[i].nxt) { int v = edge[i].to; int w = edge[i].w; int id = edge[i].id; if (d[v] > dist + w) { use[v] = id; d[v] = dist + w; cost[v] = w; qu.push(make_pair(d[v], v)); } else if (d[v] == dist + w && cost[v] > w) { cost[v] = w; use[v] = id; } } } } int main() { int n, m; scanf("%d%d", &n, &m); memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; ++i) { d[i] = (1LL << 60); cost[i] = d[i]; } tot = 0; int u, v, w, s; for (int i = 1; i <= m; ++i) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w, i); addedge(v, u, w, i); } scanf("%d", &s); Dijkstra(s); LL sum = 0; for (int i = 1; i <= n; ++i) { for (int j = head[i]; ~j; j = edge[j].nxt) { if (vis[edge[j].id]) { sum += edge[j].w; } } } cout << sum / 2 << endl; if (!sum) { return 0; } for (int i = 1; i <= m; ++i) { if (vis[i]) { printf("%d ", i); } } printf("\n"); return 0; }

首页上一页 1 2 下一页尾页 2/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++读取和存储一幅BMP图像	下一篇：hdu 1558 Segment set

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: