用floyd超时了。。。注定的事情。。。题意：看案例就跑出来了。。不需要看题了把。。
#include
#include
#include
using namespace std; #include
const int INF =1999299; int minn(int a,int b) { return a>b?b:a; } #define N 510 #define M 251000 int n, m;//n m 为点数和边数 struct Edge { int from, to, val,nex; bool sign;//是否为桥 } edge[M<<1]; int head[N], edgenum; void add(int u, int v,int val) //边的起点和终点 { Edge E= {u, v, val,head[u], false}; edge[edgenum] = E; head[u] = edgenum++; } int DFN[N], Low[N], Stack[N], top, Time; //Low[u]是点集{u点及以u点为根的子树} 中(所有反向弧)能指向的(离根最近的祖先v) 的DFN[v]值(即v点时间戳) int taj;//连通分支标号，从1开始 int Belong[N];//Belong[i] 表示i点属于的连通分支 bool Instack[N]; vector
bcc[N]; //标号从1开始 void tarjan(int u ,int fa) { DFN[u] = Low[u] = ++ Time ; Stack[top ++ ] = u ; Instack[u] = 1 ; for (int i = head[u] ; ~i ; i = edge[i].nex ) { int v = edge[i].to; if(DFN[v] == -1) { tarjan(v , u); Low[u] = minn(Low[u] ,Low[v]) ; if(DFN[u] < Low[v]) { edge[i].sign = 1;//为割桥 } } else if(Instack[v]) { Low[u] = minn(Low[u] ,DFN[v]) ; } } if(Low[u] == DFN[u]) { int now; taj ++ ; bcc[taj].clear(); do { now = Stack[-- top] ; Instack[now] = 0 ; Belong [now] = taj ; bcc[taj].push_back(now); } while(now != u) ; } } void tarjan_init(int all) { memset(DFN, -1, sizeof(DFN)); memset(Instack, 0, sizeof(Instack)); top = Time = taj = 0; for(int i=1; i<=all; i++) if(DFN[i]==-1 ) tarjan(i, i); //注意开始点标！！！ } vector
G[N]; int du[N]; void suodian() { memset(du, 0, sizeof(du)); for(int i = 1; i <= taj; i++) G[i].clear(); for(int i = 0; i < edgenum; i++) { int u = Belong[edge[i].from], v = Belong[edge[i].to]; if(u!=v) { G[u].push_back(v), du[v]++; } } } int d[N][N],cost[N][N]; void Dijkstra(int n,int beg) { bool vis[N]; for(int i=0; i<=n; i++) { d[beg][i]=INF; vis[i]=false; } d[beg][beg]=0; for(int j=1; j<=n; j++) { int k=-1; int Min=INF; for(int i=0; i<=n; i++) if(!vis[i]&&d[beg][i]