题解

Dijkstra

//#include <cjdst.h>
#include <vector>
#include <memory.h>
#include <queue>
#include <iostream>
#include <cstdio>
#define int long long 
int read(){
	char c = getchar();
	int x = 0, f = 1;
	while(!isdigit(c)){
		if(c == '-') f = -f;
		c = getchar();
	}
	while(isdigit(c)){
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x * f;
}
using namespace std;
struct node{
	int to, len, id;
	bool operator < (const node &b) const{
		return len > b.len;
	}
};
vector <node> v[200005];
int dis[200005];
bool vis[200005], vis2[200005];
int n, m, k, x, y, z;
void dijkstra(){
	memset(dis, 63, sizeof(dis));
	dis[1] = 0, vis2[0] = 1;
	priority_queue <node> q;
	q.push({1, 0, 0});
	while(!q.empty()){
		node head = q.top();
		q.pop();
		if(vis[head.to]) continue;
		vis[head.to] = 1;
		if(!vis2[head.id]) cout << head.id << ' ', vis2[head.id] = 1;
		for(node it:v[head.to]){
			if(head.len + it.len < dis[it.to]){
				dis[it.to] = head.len + it.len;
				q.push({it.to, dis[it.to], it.id});
			}
		}
	}
}
signed main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		x = read(), y = read(), z = read();
		v[x].push_back({y, z, i});
        v[y].push_back({x, z, i});
	}
	dijkstra();

	return 0;
}