|
楼主 |
发表于 2018-2-13 16:27:28
|
显示全部楼层
点的数目远远超过200,Floyd算法的时间复杂度就超过了千万级别。因此只能使用dijkstra算法
- #include<cstdio>
- #include<vector>
- #define N 1001
- using namespace std;
- struct E
- {
- int next;
- int c;
- int cost;
- };
- vector<E> edge[N];
- bool mark[N];
- int dis[N];
- int cost[N];
- int main()
- {
- int n,m;
- int S,T;
- while(scanf("%d%d",&n,&m)!=EOF)
- {
- if(n==0&&m==0) break;
- for(int i=1;i<=n;i++) edge[i].clear();
- while(m--)
- {
- int a,b,c,cost;
- scanf("%d%d%d%d",&a,&b,&c,&cost);
- E tmp;
- tmp.c=c;
- tmp.cost=cost;
- tmp.next=b;
- edge[a].push_back(tmp);
- tmp.next=a;
- edge[b].push_back(tmp);
- }
- scanf("%d%d",&S,&T);
- for(int i=1;i<=n;i++)
- {
- dis[i]=-1;
- mark[i]=false;
- }
- dis[S]=0;
- cost[S]=0;
- mark[S]=true; //点1加入集合
- int newP=S; //新加入集合的点为点1
- for(int i=1;i<n;i++)
- {
- for(int j=0;j<edge[newP].size();j++)
- {
- int t=edge[newP][j].next;
- int c=edge[newP][j].c;
- int co=edge[newP][j].cost;
- if(mark[t]==true) continue;
- if(dis[t]==-1||dis[t]>(dis[newP]+c||dis[t]==dis[newP]+c&&cost[t]>cost[newP]+co))
- {
- dis[t]=dis[newP]+c;
- cost[t]=cost[newP]+co;
- }
- }
- int min=123123123;
- for(int j=1;j<=n;j++)
- {
- if(mark[j]) continue;
- if(dis[j]==-1) continue;
- if(dis[j]<min)
- {
- min=dis[j];
- newP=j;
- }
- }
- mark[newP]=true;
- }
- printf("%d %d\n",dis[T],cost[T]);
- }
- }
复制代码 |
|