今天做了个练习赛,,这道题目主要是题意坑爹,间谍在战争时期想要传递一份邮件回国,邮件可以在各个邮局之间传播,但传递是单向的,并且耗时,如果两个邮局在一个国家的话,那么邮件在他们之间的传递不用耗时,判断两个邮局是否在一个国家的标准是两个邮局可以互相传递邮件
由于两个邮局可以互相传递邮件就是一个国家的,可以想到强连通,进行缩点操作,缩点过程中要同时维护新图的边权,会发现每个国家之间想要完成联系可以通过国内的各个邮局实现,时间代价不同,利用最短路的贪心思想,可以在过程中只保留国家之间最短的那条边
我是直接用了floyd,因为我感觉不会超时,可是超了,我不死心,我认为是哪里写错了,就乱改交了好多把,结果刚好1000ms飘过,题目要求的时间也是1000ms,我自己都不信,后来又交了几遍过的代码,又过不了了,估计是卡过去的,思路是对的,只要改成dijkstra 或者spfa就能很快过了,反正我rp不错,居然卡过了,无语的代码奉上
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #define ll long long #define eps 1e-7 #define inf 0x3f3f3f3f //const ll INF = 1ll<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::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<b) return a; else return b; } void clear() { memset(head,-1,sizeof(head)); memset(dfn,-1,sizeof(dfn)); memset(vis,0,sizeof(vis)); memset(mp,0x3f,sizeof(mp)); vis_num = 0; scc_num = 0; tot = 0; stack_num = 0; } void addedge(int u,int v,int w) { edge[tot].from = u; edge[tot].to = v; edge[tot].value = w; edge[tot].nex = head[u]; head[u] = tot++; } void tarjan(int v) { dfn[v] = low[v] = ++vis_num; vis[v] = 1; Stack[stack_num++] = v; for(int i=head[v];i!=-1;i=edge[i].nex) { int u = edge[i].to; if(dfn[u] == -1) { tarjan(u); low[v] = min(low[u],low[v]); } else if(vis[u]) low[v] = min(dfn[u],low[v]); } int tmp; if(low[v] == dfn[v]) { scc_num++; do { tmp = Stack[--stack_num]; id[tmp] = scc_num; vis[tmp] = 0; }while(tmp != v); } } void cal(int n) { for(int i=1;i<=n;i++) if(dfn[i] == -1) tarjan(i); } void floyd() { for(int k=1;k<=scc_num;k++) for(int i=1;i<=scc_num;i++) for(int j=1;j<=scc_num;j++) if(mp[i][j] > 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; }