本文共 1629 字,大约阅读时间需要 5 分钟。
这一题啊,其实还是很简单的~(A掉了就很简单啊~)
#include #include #include #include #include #include #include #include #include #include using namespace std;#define LL long long#define INF 0x3f3f3f3fconst double pi = acos(-1.0);const int mod =9973;const int N = 1010;struct asd{ int to; int w; int m; int next;};bool vis[N];int dis[N];int used[N];asd q[N*N];int tol,head[N*N];int cash[N][N];int n;queue e;void super_spfa(int s,int t){ while(!e.empty()) e.pop(); for(int i=1;i<=n;i++) { if(i!=s) { vis[i]=0; dis[i]=INF; used[i]=cash[s][i]; } }// printf("%d\n",used[3]); used[s]=0; vis[s]=1; dis[s]=0; e.push(s); while(!e.empty()) { int u=e.front();e.pop(); vis[u]=0; for(int v=head[u];v!=-1;v=q[v].next) { int i=q[v].to; // printf("i=%d\n",i); if(dis[i]>dis[u]+q[v].w) { dis[i]=dis[u]+q[v].w; used[i]=used[u]+q[v].m; if(!vis[i]) { vis[i]=1; e.push(i); } //printf("i=%d %d\n",i,used[i]); } else if(dis[i]==dis[u]+q[v].w) { if(used[i]>used[u]+q[v].m) { used[i]=used[u]+q[v].m; // printf("i=%d %d\n",used[i]); if(!vis[i]) { vis[i]=1; e.push(i); } } } } } printf("%d %d\n",dis[t],used[t]);}void add(int a,int b,int c,int d){ q[tol].to=b; q[tol].w=c; q[tol].m=d; q[tol].next=head[a]; head[a]=tol++;}int main(){ int m; int a,b,c,d,s,t; while(~scanf("%d%d",&n,&m)&&n&&m) { tol=0; memset(head,-1,sizeof(head)); for(int i=0;i
转载于:https://www.cnblogs.com/keyboarder-zsq/p/5934482.html