POJ3114 Countries in War 强连通缩点 + 最短路 - c++编程基础

今天做了个练习赛，，这道题目主要是题意坑爹，间谍在战争时期想要传递一份邮件回国，邮件可以在各个邮局之间传播，但传递是单向的，并且耗时，如果两个邮局在一个国家的话，那么邮件在他们之间的传递不用耗时，判断两个邮局是否在一个国家的标准是两个邮局可以互相传递邮件

由于两个邮局可以互相传递邮件就是一个国家的，可以想到强连通，进行缩点操作，缩点过程中要同时维护新图的边权，会发现每个国家之间想要完成联系可以通过国内的各个邮局实现，时间代价不同，利用最短路的贪心思想，可以在过程中只保留国家之间最短的那条边

我是直接用了floyd，因为我感觉不会超时，可是超了，我不死心，我认为是哪里写错了，就乱改交了好多把，结果刚好1000ms飘过，题目要求的时间也是1000ms,我自己都不信，后来又交了几遍过的代码，又过不了了，估计是卡过去的，思路是对的，只要改成dijkstra 或者spfa就能很快过了，反正我rp不错，居然卡过了，无语的代码奉上

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0x3f3f3f3f //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; typedef struct Node{ int from,to; int nex; int value; }; Node edge[510 * 500]; int head[500 + 10],low[500 + 10],dfn[500 + 10],id[500 + 10],Stack[500 + 10]; int vis[500 + 10]; int mp[500 + 10][500 + 10]; int vis_num,scc_num,tot,stack_num,tot2; int min(int a,int b) { if(a
                    
                      mp[k][j] + mp[i][k]) mp[i][j] = mp[k][j] + mp[i][k]; } int main() { int n,m; while(scanf("%d %d",&n,&m),n) { clear(); int a,b,w; while(m--) { scanf("%d %d %d",&a,&b,&w); addedge(a,b,w); } cal(n); for(int i=1;i<=n;i++) { for(int j=head[i];j!=-1;j=edge[j].nex) { int u = edge[j].to; if(id[i] != id[u]) mp[ id[i] ][ id[u] ] = min(mp[ id[i] ][ id[u] ],edge[j].value); } } for(int i=0;i<=scc_num;i++) mp[i][i] = 0; floyd(); int ques; scanf("%d",&ques); while(ques--) { scanf("%d %d",&a,&b); if(mp[ id[a] ][ id[b] ] != inf) printf("%d\n",mp[ id[a] ][ id[b] ]); else printf("Nao e possivel entregar a carta\n"); } printf("\n"); } return EXIT_SUCCESS; }