# 洛谷 P1339 [USACO09OCT]热浪Heat Wave

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677 #include #include #include #include #include #define ll long long #define pii pair #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int t, c, ts, te; struct edge {     int v, w;     edge(int vv, int ww) { v = vv; w = ww; } }; vector edges[2505]; int dis[2505]; bool inqueue[2505]; //bool visited[2505]; /* struct cmp {     bool operator () (int i1, int i2) {         return dis[i1] > dis[i2];     } }; */ void SPFA() {     queue q;     dis[ts] = 0;     inqueue[ts] = true;     q.push(ts);     while (!q.empty()) {         int node = q.front();         q.pop();         inqueue[node] = false;         for (int i = 0; i < edges[node].size(); i++) {             if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {                 dis[edges[node][i].v] = dis[node] + edges[node][i].w;                 if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);             }         }     } } /* void dijkstra() {     priority_queue,cmp> pq;     dis[ts] = 0;     pq.push(ts);     while (!pq.empty()) {         int node = pq.top();         pq.pop();         if (visited[node])continue;         visited[node] = true;         for (int i = 0; i < edges[node].size(); i++) {             if (!visited[edges[node][i].v] && dis[edges[node][i].v] > dis[node] + edges[node][i].w) {                 //有可能存在一种情况：虽然没有轮到点i成为离已处理完毕的点集最近的点，但点i的距离值已经由其它处理中或处理完毕的点多次更新，所以松弛的第二个条件必须加入，这也是为什么cmp必须要用实时的数据                 dis[edges[node][i].v] = dis[node] + edges[node][i].w;                 pq.push(edges[node][i].v);             }         }     } } */ int main() {     ios::sync_with_stdio(false);     cin >> t >> c >> ts >> te;     for (int i = 1; i <= c; i++) {         int rs, re, ci;         cin >> rs >> re >> ci;         edges[rs].push_back(edge(re, ci));         edges[re].push_back(edge(rs, ci));     }     memset(dis, 0x7f, sizeof(dis));     SPFA();     //dijkstra();     cout << dis[te]; }