Entity Framework在Asp.net MVC中的实现One Context Per Request

热浪

 

背景 Background
USACO OCT09 9TH
 
描述 Description
德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇,方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用(包括油费,过路费等等)。考虑这个有7个城镇的地图。城镇5是奶源,城镇4是终点(括号内的数字是道路的通过费用)。

                              [1]----1---[3]-
                             /               \
                      [3]---6---[4]---3--[3]--4
                     /               /       /|
                    5         --[3]--  --[2]- |
                     \       /        /       |
                      [5]---7---[2]--2---[3]---
                            |       /
                           [1]------

经过路线5-6-3-4总共需要花费3 (5->6) + 4 (6->3) + 3 (3->4) = 10的费用。

给定一个地图,包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs,终点Re (1 <= Rs <= T; 1 <= Re <= T),和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。
 
输入格式 InputFormat
* 第一行: 4个由空格隔开的整数: T, C, Ts, Te

* 第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci
 
输出格式 OutputFormat
* 第一行: 一个单独的整数表示Ts到Te的最短路的长度。(不是费用麼?怎麼突然变直白了
——译者注)数据保证至少存在一条道路。
 
样例输入 SampleInput [复制数据]

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

 

样例输出 SampleOutput [复制数据]

7

 

数据范围和注释 Hint
5->6->1->4 (3 + 1 + 3)
 
题解:
  最短路模版题
 
#include<stdio.h>
#include<stdbool.h>
#include<limits.h>
int
a[40000],b[40000],c[40000],q[20000],d[20000],f[20000];
bool
vis[20000]={false};
int
x,y,z,sum,n,m,i,s,t;

void
qsort(int head, int tail)
{
    int
    i,j,x,y,z;
    i=head;j=tail;
    x=a[head];y=b[head];z=c[head];
    while(i<j)
    {
        while((i<j)&&(a[j]>=x)) j--;
        a[i]=a[j];b[i]=b[j];c[i]=c[j];
        while((i<j)&&(a[i]<=x)) i++;
        a[j]=a[i];b[j]=b[i];c[j]=c[i];
    }
    a[i]=x;b[i]=y;c[i]=z;
    if (head<(i-1)) qsort(head,i-1);
    if ((i+1)<tail) qsort(i+1,tail);
}

void
spfa(int s)
{
  int
  i,k,head,tail;
  for (i=1;i<=n;i++)
  d[i]=INT_MAX >> 1;
  d[s]=0;
  head=0;tail=1;
  q[1]=s;
  vis[s]=true;
  
  while (head<tail)
  {
    head=head%10000+1;
    k=q[head];
    for (i=f[k];i<=(f[k+1]-1);i++)
    if ((d[k]+c[i])<d[b[i]])
    {
        d[b[i]]=d[k]+c[i];
        if (vis[b[i]]==false)
        {
            tail=tail%10000+1;
            q[tail]=b[i];
            vis[b[i]]=true;
        }
    }
    vis[k]=false;
  }
}

int
main(void)
{
    scanf("%d%d%d%d\n",&n,&m,&s,&t);
    sum=0;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        sum++;
        a[sum]=x;
        b[sum]=y;
        c[sum]=z;
        sum++;
        b[sum]=x;
        a[sum]=y;
        c[sum]=z;
    }
    m=m*2;
    qsort(1,m);
    for(i=1;i<=m;i++)
    if (f[a[i]]==0) f[a[i]]=i;
    f[n+1]=m+1;
    for (i=n;i>=1;i--)
    if (f[i]==0) f[i]=f[i+1];
    spfa(s);
    printf("%d\n",d[t]);
    return 0;
}

 

Entity Framework在Asp.net MVC中的实现One Context Per Request(转),古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。