- 1#include
- 2#include
- 3#include <string.h> 4#include
- 5#include 6 #defineREAD() freopen("in.txt", "r", stdin); 7 #defineMAXV 2007 8 #defineMAXE 20007 9 #defineINF 0x3f3f3f3f3f3f3f3f10
- 11 using namespace std;
- 12 int N, M;
- 13typedeflong long ll;
- 14typedef pairint> P;
- 15
- 16 struct Edge
- 17 {
- 18 int to, next;
- 19 ll cost;
- 20 Edge() {}
- 21Edge(intto, ll cost,int next) : to(to), cost(cost), next(next) {}
- 22 }edge[MAXE];
- 23
- 24 int head[MAXV];
- 25 intnum =0;
- 26 voidAdd(int from,int to, ll cost)
- 27 {
- 28edge[num] = Edge(to, cost, head[from]);
- 29head[from] = num++;
- 30 }
- 31
- 32 int prim()
- 33 {
- 34 ll dist[MAXV];
- 35ll rec[MAXV], r =0;
- 36 bool use[MAXV];
- 37priority_queue, greater
- > que;
- // 从小到大排啊
- 38fill(dist, dist+MAXV, INF);
- 39fill(use, use+MAXV,false);
- 40dist[1] =0;
- 41que.push(P(dist[1],1));
- 42 while(!que.empty())
- 43 {
- 44P p = que.top();
- 45 que.pop();
- 46ll d = p.first;
- 47 intv = p.second;
- 48 if(!use[v]) rec[r++] = dist[v];
- 49use[v] =true;
- 50 if(dist[v] < d)continue;
- 51 intt = head[v];
- 52 while(t != -1)
- 53 {
- 54Edge e = edge[t];
- 55 if(!use[e.to] && dist[e.to] > e.cost)
- 56 {
- 57dist[e.to] = e.cost;
- 58 que.push(P(dist[e.to], e.to));
- 59 }
- 60t = e.next;
- 61 }
- 62 }
- 63sort(rec, rec+r);
- 64 returnrec[r-1];
- 65 }
- 66
- 67
- 68
- 69 int main()
- 70 {
- 71 READ()
- 72scanf("%d%d", &N, &M);
- 73memset(edge, -1,sizeof(edge));
- 74memset(head, -1,sizeof(head));
- 75 for(inti =0; i < M; i++)
- 76 {
- 77 int from, to;
- 78 ll cost;
- 79scanf("%d%d", &from, &to);
- 80scanf("%lld", &cost);
- 81Add(from, to, cost);
- 82Add(to,from, cost);
- 83 }
- 84ll ans = prim();
- 85cout << ans << endl;
- 86}
来源: http://www.bubuko.com/infodetail-1954324.html