1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include<algorithm> #include<cmath> #include<queue> #include<vector> using namespace std; struct Node { int to; long long len; bool operator<(const Node &a) const { return len > a.len; } }; bool isUsed[510]; long long ans[510]; vector<Node> NodeQueue[510]; void addEdge(int s, int e, int len) { NodeQueue[s].push_back((Node){e,len}); NodeQueue[e].push_back((Node){s,len}); } int n,m; priority_queue<Node> PriNodeQueue; int main() { scanf("%d%d", &n, &m); while(m--) { int s, e, len; scanf("%d%d%d",&s, &e, &len); if(s != e) addEdge(s, e, len); } int s, t; scanf("%d%d", &s, &t); for(int i = 0; i < 505; i++) ans[i] = 999999999999; ans[s] = 0; PriNodeQueue.push((Node){s,0}); while(!PriNodeQueue.empty()){ Node now = PriNodeQueue.top(); PriNodeQueue.pop(); int u = now.to; if(!isUsed[u]){ isUsed[u] = true; for(int i = 0; i < NodeQueue[u].size(); i++){ if(!isUsed[NodeQueue[u][i].to]){ int v = NodeQueue[u][i].to; int len = NodeQueue[u][i].len; if(ans[v] > ans[u] + len) { ans[v] = ans[u] + len; PriNodeQueue.push((Node){v,ans[v]}); } } } } } printf("%lld",ans[t]); return 0; }
|