解题：很暴力的spfa
压线过了。。
View Code
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<queue> #include<cstring> #define maxn 2500 using namespace std; //const int maxn=10000; //typedef pair<int,int >pii; //typedef pair<pii,int>pp; //vector<pp>mm[maxn]; int n,m,L; typedef long long ll; int dis[maxn]; int head[maxn]; struct node0 { int v; int next; int c; }node[maxn]; int visit[maxn]; int sum; void add(int u,int v,int c) { sum++; node[sum].next=head[u]; head[u]=sum; node[sum].v=v; node[sum].c=c; } ll spfa(int s,int id) { for(int i=1;i<=n;i++) dis[i]=L; memset(visit,0,sizeof(visit)); dis[s]=0; //visit[s]=1; queue<int>q; q.push(s); while(!q.empty()) { int v=q.front(); q.pop(); visit[v]=0; for(int i=head[v];i!=-1;i=node[i].next) //if(mm[v][i].second!=id) if(i/2!=id) // if(dis[mm[v][i].first.first]>mm[v][i].first.second+dis[v]) if(dis[node[i].v]>dis[v]+node[i].c) { //dis[mm[v][i].first.first]=dis[v]+mm[v][i].first.second; dis[node[i].v]=dis[v]+node[i].c; // if(!visit[mm[v][i].first.first]) if(!visit[node[i].v]) { //visit[mm[v][i].first.first]=1; //q.push(mm[v][i].first.first); visit[node[i].v]=1; q.push(node[i].v); } } } ll ans=0; for(int i=1;i<=n;i++) ans+=dis[i]; return ans; } ll solve(int id) { ll ans=0; for(int i=1;i<=n;i++) { ans+=spfa(i,id); } return ans; } int main() { //freopen("f:\\1.txt","r",stdin); while(scanf("%d%d%d",&n,&m,&L)!=EOF) { //for(int i=1;i<=n;i++) // mm[i].clear(); memset(head,-1,sizeof(head)); sum=-1; for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); // mm[a].push_back(pp(pii(b,c),i)); //mm[b].push_back(pp(pii(a,c),i)); } ll ans1,ans2,temp; ans1=solve(-1); ans2=ans1; for(int i=0;i<m;i++) { temp=solve(i); if(temp>ans2) ans2=temp; } printf("%lld %lld\n",ans1,ans2); } // fclose(stdout); return 0; }