幻想道路(最短路径)

幻想道路

时间限制: 1 Sec 内存限制: 128 MB

题目描述

幻想世界最近发生了几件大事，先是有快乐星球代表，再是有黑暗星球代表来到了幻想世界，他们在幻想世界建造了一个自己的王国，并带领了一大批自己星球上的人入驻。
对于这两个新的伙伴，原来的幻想王国里的人们还不知道应该以怎样的态度去应对。但阿卡表示，不管快乐星球与黑暗星球多么的势不两立，这都不关他们的事，他们还是要与两个星球之间都建一些道路通行。
幻想世界原来有n个王国，他们之间已经有了m条道路，这些道路都是双向的。阿卡决定为两个星球的到来再新建Q条路，这样一来，有些王国就能够同时到达快乐星球与黑暗星球了。
幻想世界还有一条规定，就是每条路都有一个路霸，他会在这条路上收买路钱，但新建的Q条路暂时还没有出现这种情况。每个路霸知道，所有的居民都对这两个新到来的星球十分的感兴趣，如果自己这条路不能到达黑暗星球或者不能到达快乐星球，那么经过这条路的居民就会大大减少，就收不到多少买路钱了。另外，就算这条路能同时达到两个星球，他能收的买路钱也跟经过这条路的快乐星球到达黑暗星球的最短路径有关。
这下这些路霸们着急了，他们找到了你，想让你帮忙计算一下他们关心的事。

输入

第一行一个整数n，表示幻想王国的数量。
第二行两个数m，Q。m表示原来幻想王国之间边的数量，Q表示新建的边的数量。
接下来m行，每行三个数u,v,w。表示这条路连接u,v两个王国，这条路的长度是w。
保证1≤u,v≤n。
接下来Q行，每行三个数u,v,w。表示这条路连接u,v两个王国，这条路的长度是w。
其中u>n或者v>n。n+1号王国表示快乐星球，n+2号王国表示黑暗星球。

输出

输出m行，每行表示一条道路。
如果这条道路不能同时达到快乐星球和黑暗星球，那么输出一行“GG”。
否则输出一个数，表示经过这条道路的快乐星球到黑暗星球之间的最短路。

样例输入

复制样例数据

样例输出

12
11
15

提示

对于100%的数据，n,m,Q≤104,0<w≤100。

我们要求的是每一条边是否可以由快乐星球通过这条边到黑暗星球。

那么将每一条边看成两个点，然后是从快乐星球到一个点的最短路+这条边的长度+从另个点到黑暗星球的最短路，有两种可能情况，求2次最短路就行了。然后这道题目我交了接近30遍。。。为啥，因为int u,v,w是错的，要初始化下，为int u = 0, v = 0, w = 0....我也不知道为啥。。。我气得吐血。。。

wo我用的是优化版的dijkstral。。。

// /**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
  
typedef long long LL;
using namespace std;
  
const int inf = 0x3f3f3f3f;
int n, m, q;
int vis[10005], from[10005], to[10005], w[10005];
int dist[10005];
  
  
pair<int, int> p1[10005], p2[10005];
  
struct node
{
    int v, w;
    int dist;
    bool operator <(const node &x)const{
        return dist == x.dist ? w > x.w : dist > x.dist;
    }
}ed[40005];
  
vector<node>vec[10005];
  
void dijkstral(int x){
    for (int i = 1; i <= x; i++){
        dist[i] = inf;
        vis[i] = 0;
    }
    dist[x] = 0;
    priority_queue<node> q;
    q.push(node{x, 0, 0});
    while(q.size()){
        node t = q.top();
        q.pop();
        if(vis[t.v]) continue;
        vis[t.v] = 1;
        int len = vec[t.v].size();
        for (int i = 0; i < len; i++){
            int v = vec[t.v][i].v, we = vec[t.v][i].w;
            if(!vis[v] && dist[v] >= dist[t.v] + we){
                dist[v] = dist[t.v] + we;
                q.push(node{v, we, dist[v]});
            }
        }
    }
}
  
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
  
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= m; i++){
        scanf("%d %d %d", &from[i], &to[i], &w[i]);
        vec[from[i]].push_back(node{to[i], w[i], 0});
        vec[to[i]].push_back(node{from[i], w[i], 0});
    }
    int u = 0, v = 0, we = 0;
    //int u, v, we;
    for (int i = 1; i <= q; i++){
        scanf("%d %d %d", &u, &v, &we);
        vec[u].push_back(node{v, we, 0});
        vec[v].push_back(node{u, we, 0});
    }
    dijkstral(n + 1);
    for (int i = 1; i <= m; i++){
        p1[i].first = dist[from[i]];
        p2[i].second = dist[to[i]];
    }
    dijkstral(n + 2);
    for (int i = 1; i <= m; i++){
        p1[i].second = dist[to[i]];
        p2[i].first = dist[from[i]];
    }
    for (int i = 1; i <= m; i++){
        int minn = inf;
        if(p1[i].first != inf && p1[i].second != inf){
            minn = min(minn, p1[i].first + p1[i].second + w[i]);
        }
        if(p2[i].first != inf && p2[i].second != inf){
            minn = min(minn, p2[i].first + p2[i].second + w[i]);
        }
        if(minn == inf) printf("GG\n");
        else printf("%d\n", minn);
    }
  
    return 0;
}
/**/